The Barto–Opršal–Pinsker tractability dichotomy conjecture for reducts of finitely bounded homogeneous structures

Let \relB\rel B be a reduct of a finitely bounded homogeneous structure. A uniformly continuous minion homomorphism is a map from Pol(\relB)\operatorname{Pol}(\rel B) to Proj\operatorname{Proj} preserving the minion operations and uniformly continuous with respect to the natural topology.

Barto–Opršal–Pinsker dichotomy conjecture. Exactly one of the following holds:

  1. There exists a uniformly continuous minion homomorphism from Pol(\relB)\operatorname{Pol}(\rel B) to Proj\operatorname{Proj}, and CSP(\relB)\operatorname{CSP}(\rel B) is NP\textsf{NP}-complete.
  2. Pol(\relB)\operatorname{Pol}(\rel B) does not have a uniformly continuous minion homomorphism to Proj\operatorname{Proj}, and CSP(\relB)\operatorname{CSP}(\rel B) is in P\textsf{P}.

This is a formulation of the infinite-domain tractability dichotomy conjecture for first-order reducts of finitely bounded homogeneous structures. It has been verified in numerous special cases, but the general dichotomy remains open.

Sources & referencesView supporting material

Primary source

Manuel Bodirsky, Antoine Mottet, Miroslav Olšák, Jakub Opršal, Michael Pinsker and Ross Willard, “Topology is relevant (in a dichotomy conjecture for infinite-domain constraint satisfaction problems)”, arXiv:1901.04237 (2019).

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.