Hardness of monadic second-order formulae over succinct graphs

2023/02/09 by Gamard, Guilhem, Goubault-Larrecq, Aliénor, Guillon, Pierre +3 · 2 citations
#05C #68 #Computational Complexity (cs.CC) #F.2 #F.4 #FOS: Computer and information sciences #G.2.2 #Logic in Computer Science (cs.LO)

paper · doi:10.48550/arxiv.2302.04522

Abstract

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.

Cited by

• Complexity lower bounds for succinct binary structures of bounded clique-width with restrictions
• Circuit metaconstruction in logspace for Rice-like complexity lower bounds in ANs and SGRs

Related

• Lower Bounds for the Complexity of Monadic Second-Order Logic
• Computability by Monadic Second-Order Logic
• Expanding the expressive power of Monadic Second-Order logic on restricted graph classes
• Where First-Order and Monadic Second-Order Logic Coincide
• Courcelle's Theorem Without Logic