The core-free finite tractability conjecture via height-1 clone homomorphisms

About 11 years old · traced to

Let A\mathbb{A} be a finite relational structure, and let A\mathscr{A} be its polymorphism clone. Let 1\mathbf{1} be the clone of projections on a two-element set, and let an h1 clone homomorphism mean a homomorphism preserving identities of height 11. Core-free finite tractability conjecture. One of the following holds: A\mathscr{A} maps to 1\mathbf{1} via an h1 clone homomorphism, in which case CSP⁡(A)\operatorname{CSP}(\mathbb{A}) is NP-complete, or CSP⁡(A)\operatorname{CSP}(\mathbb{A}) is solvable in polynomial time. This is the core-free reformulation of the finite tractability conjecture, enabled by the equivalence between the relevant clone-homomorphism, cyclic-operation, and Siggers-operation conditions.

References

Primary source

Libor Barto, Jakub Opršal and Michael Pinsker, “The wonderland of reflections”, arXiv:1510.04521 (2017).

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.