The finitely bounded homogeneous CSP dichotomy conjecture

Let A\mathbb A be a CSP template that is a first-order reduct of a countable finitely bounded homogeneous structure B\mathbb B. Let Pol(A)\operatorname{Pol}(\mathbb A) denote the polymorphism clone of A\mathbb A, let P\mathscr P be the clone of projections, and let CSP(A)\operatorname{CSP}(\mathbb A) denote the constraint satisfaction problem for A\mathbb A.

Finitely bounded homogeneous CSP dichotomy conjecture. Exactly one of the following holds: either Pol(A)\operatorname{Pol}(\mathbb A) has a uniformly continuous minion homomorphism to P\mathscr P and CSP(A)\operatorname{CSP}(\mathbb A) is NP-complete, or Pol(A)\operatorname{Pol}(\mathbb A) has no uniformly continuous minion homomorphism to P\mathscr P and CSP(A)\operatorname{CSP}(\mathbb A) 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

Never refreshed

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.