Authors: Guilhem Gamard ^1,2,3,4; Aliénor Goubault-Larrecq ⁵; Pierre Guillon ⁶; Pierre Ohlmann ⁵; Kévin Perrot ⁵; Guillaume Theyssier ⁶

• 1 Laboratoire Lorrain de Recherche en Informatique et ses Applications
• 2 Université de Lorraine
• 3 Centre National de la Recherche Scientifique
• 4 Inria MOCQUA
• 5 Laboratoire d’Informatique et Systèmes
• 6 Institut de Mathématiques de Marseille

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.