The model-complete-core CSP dichotomy conjecture
The model-complete-core CSP dichotomy conjecture
Let be a reduct of a finitely bounded homogeneous structure, and let be its model-complete core. Let be the finite structure defined by
A structure pp-interprets another with parameters when the latter has a primitive-positive interpretation in the former using parameters.
Model-complete-core CSP dichotomy conjecture. One of the following holds:
- pp-interprets with parameters, and consequently is NP-complete.
- is polynomial-time solvable.
The first alternative is known to imply NP-completeness; the conjecture asserts tractability in the complementary case. The source presents this as the older dichotomy conjecture for reducts of finitely bounded homogeneous structures and relates its proposed tractability criterion to Siggers identities modulo outer embeddings.
Sources & referencesView supporting material
Primary source
Libor Barto, Michael Kompatscher, Miroslav Olšák, Trung Van Pham and Michael Pinsker, “Equations in oligomorphic clones and the Constraint Satisfaction Problem for ω-categorical structures”, arXiv:1612.07551 (2018).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.