The totally symmetric polymorphism conjecture for omega-categorical CSPs
The totally symmetric polymorphism conjecture for omega-categorical CSPs
Let be an -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 has totally symmetric polymorphisms of all arities, then
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
Sign in to submit a solution.
No solutions have been posted yet.