Beyond dichotomies: Constraint Satisfaction over stable ω-categorical structures
- 14:00 19th November 2026 ( week 6, Michaelmas Term 2026 )Room 051
For a fixed relational structure A (the template), the constraint satisfaction problem CSP(A) asks whether a given finite structure admits a homomorphism to A. For finite templates, the theorem of Bulatov and Zhuk states that each CSP is in P or NP-complete. For infinite structures, ω-categoricity provides finiteness up to symmetry, while stability excludes definable order patterns. We investigate whether these conditions impose analogous restrictions on computational complexity.
We present countable stable ω-categorical structures with at most two binary relations whose CSPs exhibit three distinct behaviours: NP-complete, decidable but outside NP, and undecidable. The construction produces continuum many stable ω-categorical graphs with pairwise distinct ages—their collections of finite induced substructures. We explain how finite graphs of large girth and prescribed density distinguish the ages of these controlled Hrushovski constructions. Expanding the graphs by the non-edge relation then yields continuum many distinct CSPs, all but countably many of which are undecidable. Effective choices of the construction parameter also yield decidable CSPs beyond any prescribed time-constructible bound.
This is joint work with Manuel Bodirsky, David Bradley-Williams, and Ehud Hrushovski.
Preprint: arXiv:2610.19940