Bodirsky–Pinsker tractability conjecture for reducts of finitely bounded homogeneous structures

About 11 years old · traced to

Let fmathbbAfmathbb A be a finite-signature reduct of a finitely bounded homogeneous structure. Let fmathbbCfmathbb C be an expansion of the model-complete core of fmathbbAfmathbb A by finitely many constants, and let Pol⁡(fmathbbC)\operatorname{Pol}(fmathbb C) denote its polymorphism clone. Let fmathscrPfmathscr P denote the clone of projections.

Bodirsky–Pinsker tractability conjecture. If the model-complete core of fmathbbAfmathbb A has no such expansion fmathbbCfmathbb C for which Pol⁡(fmathbbC)\operatorname{Pol}(fmathbb C) has a continuous clone homomorphism to fmathscrPfmathscr P, then

CSP⁡(fmathbbA) is in P.\operatorname{CSP}(fmathbb A)\text{ is in P}.

This is the infinite-domain tractability conjecture for reducts of finitely bounded homogeneous structures, attributed in the source to Bodirsky and Pinsker. The supplied text does not state whether it has been resolved.

References

Primary source

Manuel Bodirsky and Antoine Mottet, “A Dichotomy for First-Order Reducts of Unary Structures”, arXiv:1601.04520 (2018).

Additional references

2 papers in this index state this conjecture (2015–2016). The statement above is taken from the most recent of them; the others are arXiv:1510.04521.

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.