The totally symmetric polymorphism conjecture for omega-categorical CSPs

From papers

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.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

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

Solutions 0

No solutions have been posted yet.