pipette
ENEnglish

A Non-Dichotomy for CSPs of Stable -Categorical Structures

Manuel Bodirsky, David Bradley-Williams, Ehud Hrushovski, Christoph Spiess

Preprint

En palabras de los autores

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 for suitable irrational parameters . Some of these graphs have NP-complete CSPs. Expanding the graphs by the non-edge relation turns age membership into a restriction of the CSP. For every time-constructible bound , there is such an expansion whose CSP is decidable but not in DTIME. For an explicit parameter , the restriction to complete instances belongs to and the full CSP belongs to . Separating the ages of the using graphs with large girth and prescribed density yields distinct CSPs of these expansions, all but countably many of which are undecidable.

Resultado principalEl resumen no menciona limitaciones.

Apareció: jueves, 15 de octubre. arXiv. Preprint, todavía sin revisión por pares.

Comentario de los autores: 35 pages