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