The homomorphic-equivalence CSP dichotomy conjecture
Statement
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.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.