The dichotomy conjecture for constraint satisfaction problems of reducts

Let Δ\Delta be a finitely bounded homogeneous structure, and let Γ\Gamma be a finite-language reduct of Δ\Delta. The constraint satisfaction problem of Γ\Gamma is denoted by CSP(Γ)\operatorname{CSP}(\Gamma).

Dichotomy conjecture. CSP(Γ)\operatorname{CSP}(\Gamma) 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

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.