The totally symmetric polymorphism conjecture for omega-categorical CSPs

At least 14 years old · documented by

Let Γ\Gamma be an ω\omega-categorical structure with finite relational signature. A family of totally symmetric polymorphisms consists of polymorphisms of every arity whose value is invariant under every permutation of the arguments. The totally symmetric polymorphism conjecture. If Γ\Gamma has totally symmetric polymorphisms of all arities, then

CSP⁡(Γ)\operatorname{CSP}(\Gamma)

can be solved in polynomial time. This is proposed as a generalization beyond the sub-exponential case, where the paper describes a classification and an efficient sampling algorithm; the conjecture remains open in the source.

References

Primary source

Manuel Bodirsky, Dugald Macpherson and Johan Thapper, “Constraint Satisfaction Tractability from Semi-lattice Operations on Infinite Sets”, arXiv:1111.6616 (2011).

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.