一句话：证明 succinct 图上 cw-nontrivial MSO 性质为 NP-hard 或 coNP-hard。
本文研究以 succinct 表示给出的图上一元二阶（MSO）性质的复杂度。succinct 图用计算邻接关系的布尔电路表示。主要结果是 Courcelle 元定理的紧致反面：对任意 cw-nontrivial 的 MSO 性质——即存在无穷多个有界 cliquewidth 的模型与反模型——要么 NP-hard，要么 coNP-hard。作者进一步考察去掉 cw-nontriviality 条件后的情形，证明在某个合理的复杂度假设下，上述二分法失效，甚至对一阶逻辑可表达的问题也成立。
Our main result is a succinct counterpoint to Courcelle's meta-theorem as follows: every cw-nontrivial monadic second-order (MSO) property is either NP-hard or coNP-hard over graphs given by succinct representations. Succint representations are Boolean circuits computing the adjacency relation. Cw-nontrivial properties are those which have infinitely many models and infinitely many countermodels with bounded cliquewidth. Moreover, we explore what happens when the cw-nontriviality condition is dropped and show that, under a reasonable complexity assumption, the previous dichotomy fails, even for questions expressible in first-order logic.
DOI 原文 · arXiv · PDF（开放获取） · DBLP
@article{abs-2302-04522,
title = {Hardness of monadic second-order formulae over succinct graphs},
author = {Guilhem Gamard and Aliénor Goubault-Larrecq and Pierre Guillon and Pierre Ohlmann and Kévin Perrot and Guillaume Theyssier},
journal = {Logical Methods in Computer Science},
volume = {Volume 22, Issue 1},
year = {2026},
doi = {10.46298/lmcs-22(1:3)2026}
}