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

About 7 years old · traced to

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.

References

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.