Algebraic approach to constraint satisfaction

Summary

The algebraic approach studies the constraint satisfaction problem of a fixed finite structure through the polymorphisms of that structure. Its basic fact is that the complexity of the problem depends only on the clone of polymorphisms. Polymorphisms satisfying good identities, such as Taylor, Siggers or cyclic identities, give efficient algorithms. The approach led to the proof of the CSP dichotomy theorem: every such problem is either in polynomial time or NP-complete.