Constraints, Complexity, and Polymorphisms
by
Peter Jeavons
Oxford University Computing Laboratory

Many natural combinatorial problems can be expressed as "constraint satisfaction problems", so this class of problems has received a lot of attention within Computer Science. Although these problems are NP-hard in general, certain restrictions on the form of the constraints can ensure tractability. By considering the algebra of polymorphisms associated with constraint relations we can translate questions about the computational complexity of this kind of problem into questions about the associated algebra. The talk will provide an introduction to this approach and some results and open questions.

Date received: February 4, 2002