A Non-Dichotomy for CSPs of Stable $ω$-Categorical Structures
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)$.…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.19940
curl -X POST /api/v1/records/arxiv/2610.19940/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.19940/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'