A Non-Dichotomy for CSPs of Stable $\omega$-Categorical Structures

Manuel Bodirsky, David Bradley-Williams, Ehud Hrushovski +1

We construct countable, stable, $\omega$-categorical structures with at most two binary relations whose CSPs exhibit three complexity regimes: NP-complete, decidable but not in NP, and…