The dichotomy conjecture for constraint satisfaction problems of reducts
The dichotomy conjecture for constraint satisfaction problems of reducts
Let be a finitely bounded homogeneous structure, and let be a finite-language reduct of . The constraint satisfaction problem of is denoted by .
Dichotomy conjecture. is either in P or NP-complete.
Complete classifications with this dichotomy were known for the empty structure, the rationals with their usual order, and the random graph. The conjecture proposes that the same P-versus-NP-complete classification holds for every finite-language reduct of a finitely bounded homogeneous structure; membership in NP is already known in this setting.
Sources & referencesView supporting material
Primary source
Michael Pinsker, “Algebraic and model theoretic methods in constraint satisfaction”, arXiv:1507.00931 (2015).
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.