{"id":"arxiv/2610.19940","url":"https://arxiv.org/abs/2610.19940","tags":["cs.LO","math.LO"],"score":0,"title":"A Non-Dichotomy for CSPs of Stable $ω$-Categorical Structures","domain":"cs.LO","source":"arxiv","authors":["Manuel Bodirsky","David Bradley-Williams","Ehud Hrushovski","Christoph Spiess"],"reviews":0,"subject":"cs.LO","summary":"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)$.…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-10-14","reactions":{}}