  Our main result is a succinct counterpoint to Courcelle's meta-theorem as
follows: every arborescent 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.
Arborescent properties are those which have infinitely many models and
countermodels with bounded treewidth. Moreover, we explore what happens when
the arborescence condition is dropped and show that, under a reasonable
complexity assumption, the previous dichotomy fails, even for questions
expressible in first-order logic.
