Cyclic and symmetric polymorphisms and CSPs
19/12/2012 Quarta-feira, 19 de Dezembro de 2012, 15:00, FCUL - Sala 6.2.45
Catarina Carvalho (School of Physics, Astronomy and Mathematics, University of Hertfordshire)
Faculdade de Ciências da Universidade de Lisboa
The existence of symmetric polymorphisms of all arities has been shown recently, by Kun et al., to be equivalent to the existence of a set operation in a structure $\Gamma$, which was known to be equivalent to CSP($\Gamma$) being solved by a width-1 algorithm.
We give an example of a relational structure with cyclic operations of all arities but no symmetric operations of all arities, and discuss its implications on the complexity of CSPs and related problems.