The model-complete-core CSP dichotomy conjecture

Let A\mathbb{A} be a reduct of a finitely bounded homogeneous structure, and let B\mathbb{B} be its model-complete core. Let S\mathbb{S} be the finite structure defined by

S:=({0,1};{(0,0,1),(0,1,0),(1,0,0)}).\mathbb{S}:=(\{0,1\};\{(0,0,1),(0,1,0),(1,0,0)\}).

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:

  1. B\mathbb{B} pp-interprets S\mathbb{S} with parameters, and consequently CSP(A)\operatorname{CSP}(\mathbb{A}) is NP-complete.
  2. CSP(A)\operatorname{CSP}(\mathbb{A}) 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

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.