The core-free finite tractability conjecture via height-1 clone homomorphisms
Let be a finite relational structure, and let be its polymorphism clone. Let be the clone of projections on a two-element set, and let an h1 clone homomorphism mean a homomorphism preserving identities of height . Core-free finite tractability conjecture. One of the following holds: maps to via an h1 clone homomorphism, in which case is NP-complete, or 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
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.