The homomorphic-equivalence CSP dichotomy conjecture

From papers

Let A\mathbb{A} be a reduct of a finitely bounded homogeneous structure. 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 is homomorphically equivalent to another when homomorphisms exist in both directions, and a primitive-positive interpretation is an interpretation defined by primitive-positive formulas.

Homomorphic-equivalence CSP dichotomy conjecture. One of the following holds:

  1. S\mathbb{S} is homomorphically equivalent to a structure with a pp-interpretation in A\mathbb{A}, and consequently CSP(A)\operatorname{CSP}(\mathbb{A}) is NP-complete.
  2. CSP(A)\operatorname{CSP}(\mathbb{A}) is polynomial-time solvable.

This is the younger dichotomy conjecture described in the source. It seeks to avoid passing first to a model-complete core; the paper proves that the two conjectures are equivalent, while the general dichotomy remains unresolved.

Progress summary

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

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).

Solutions 0

No solutions have been posted yet.