The finitely bounded homogeneous CSP dichotomy conjecture
The finitely bounded homogeneous CSP dichotomy conjecture
Let be a CSP template that is a first-order reduct of a countable finitely bounded homogeneous structure . Let denote the polymorphism clone of , let be the clone of projections, and let denote the constraint satisfaction problem for .
Finitely bounded homogeneous CSP dichotomy conjecture. Exactly one of the following holds: either has a uniformly continuous minion homomorphism to and is NP-complete, or has no uniformly continuous minion homomorphism to and is in P.
This conjecture extends the finite-domain CSP dichotomy to first-order reducts of countable finitely bounded homogeneous structures. The surrounding discussion presents it as a modern formulation incorporating recent progress; the supplied text does not establish whether the full statement is resolved.
Sources & referencesView supporting material
Primary source
Antoine Mottet and Michael Pinsker, “Smooth approximations and CSPs over finitely bounded homogeneous structures”, arXiv:2011.03978 (2021).
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
Sign in to submit a solution.
No solutions have been posted yet.