The homomorphic-equivalence CSP dichotomy conjecture
The homomorphic-equivalence CSP dichotomy conjecture
Let be a reduct of a finitely bounded homogeneous structure. Let be the finite structure defined by
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:
- is homomorphically equivalent to a structure with a pp-interpretation in , and consequently is NP-complete.
- 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
Sign in to submit a solution.
No solutions have been posted yet.