The constraint satisfaction problem and universal algebra

Many classical problems in algorithmics, such as graph coloring and 3-satisfiability, can be expressed as special cases of the constraint satisfaction problem (CSP) by restricting the allowed constraint types to some set of relations on the set of values. The general CSP is NP-complete, but it is of interest which sets of relations cause the restricted CSP to be either tractable or NP-complete. A useful invariant has turned out to be the algebra whose operations are those that preserve all the allowed constraint relations. It appears that the computational complexity of CSPs is closely linked to deep universal algebraic properties of the related algebra. In my talk, I will give a brief introduction to this area of research.