**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.