Stable omega categorical structures show three complexity types in constraint problems
A Non-Dichotomy for CSPs of Stable $ω$-Categorical Structures
Logic in Computer Science
Summary
This paper shows that for certain mathematical structures used in logic and computing, the problems of deciding constraints can be much more complicated than previously thought. The authors construct examples where these problems fall into three distinct levels: some are hard but possible to solve quickly, others are solvable but take very long, and some cannot be solved at all by any algorithm. They do this by carefully building special graphs and expanding them with additional relations, revealing a rich landscape of problem difficulties.
What this means in practice
- •For complexity theorists: Distinguish which omega-categorical constraint problems can be classified by complexity levels beyond NP, influencing complexity class research.
- •For automated reasoning developers: Guide design of constraint solvers by identifying problem templates where classical complexity boundaries do not hold, aiding solver specialization.
A theory result. No direct application yet.
Authors
Manuel Bodirsky, David Bradley-Williams, Ehud Hrushovski, Christoph Spiess
Abstract
We construct countable, stable, $ω$-categorical structures with at most two binary relations whose CSPs exhibit three complexity regimes: NP-complete, decidable but not in NP, and undecidable. The templates arise from a controlled Hrushovski construction of stable $ω$-categorical graphs $M_α$ for suitable irrational parameters $α>1$. Some of these graphs have NP-complete CSPs. Expanding the graphs $M_α$ by the non-edge relation turns age membership into a restriction of the CSP. For every time-constructible bound $t$, there is such an expansion whose CSP is decidable but not in DTIME$(t)$. For an explicit parameter $α$, the restriction to complete instances belongs to $\mathrm{coNP}$ and the full CSP belongs to $Σ_2^{\mathrm P}$. Separating the ages of the $M_α$ using graphs with large girth and prescribed density yields $2^{\aleph_0}$ distinct CSPs of these expansions, all but countably many of which are undecidable.