A Non-Dichotomy for CSPs of Stable ω-Categorical Structures
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 coNP and the full CSP belongs to Σ2P. Separating the ages of the Mα using graphs with large girth and prescribed density yields 2ℵ0 distinct CSPs of these expansions, all but countably many of which are undecidable.
Related
- Univalent Non-Associative Categorical Structures
- Freely Generated Categorical Structures and Automatic Differentiation, PhD Thesis (Introduction and Conclusion)
- Complex and Stable Complex Structures on Real Vector Bundles over Connected Sums of Quaternionic Projective Planes
- Stable Complex Structures On Real Vector Bundles Over Connected Sums Of Quaternionic Projective Spaces
- Conformal structures and rigidity of complete stable minimal hypersurfaces
BibTeX
@misc{bodirsky2026nondichotomy,
title = {{A Non-Dichotomy for CSPs of Stable $ω$-Categorical Structures}},
author = {Manuel Bodirsky and David Bradley-Williams and Ehud Hrushovski and Christoph Spiess},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.19940},
eprint = {2610.19940},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.19940},
}
RIS
TY - UNPB
TI - A Non-Dichotomy for CSPs of Stable ω-Categorical Structures
AU - Manuel Bodirsky
AU - David Bradley-Williams
AU - Ehud Hrushovski
AU - Christoph Spiess
PY - 2026
DA - 2026/10/14
PB - arXiv
DO - 10.48550/arxiv.2610.19940
UR - https://arxiv.org/abs/2610.19940
AB - 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 coNP and the full CSP belongs to Σ_2^P. Separating the ages of the M_α using graphs with large girth and prescribed density yields 2^ℵ_0 distinct CSPs of these expansions, all but countably many of which are undecidable.
ER -