The complexity of constraint satisfaction: an algebraic approach
Andrei A. Bulatov
Oxford University Computing Laboratory
Oxford, UK

Abstract : A constraint satisfaction problem (CSP) is a way of expressing simultaneous requirements for values of variables. A large variety of problems in Discrete Mathematics, Computer Science and Artificial Intelligence can be viewed as special cases of the constraint satisfaction problem. Some examples are scheduling, image-processing, and frequency assignment problems, evaluation of conjunctive queries from database theory, the classic satisfiability problem from propositional logic, and many problems from graph theory, including the colorability problem.

Constraints are usually specified by means of relations. Hence the general constraint satisfaction problem can be parameterised according to the relations allowed in an instance. The problem of classifying the complexity of CSPs relative to the set of allowed relations has recently attracted the attention of many researchers. It appears that one of the most prolific approaches to this problem is the algebraic one. This approach uses clones and finite universal algebras for finite-valued constraints.

We exhibit connections between the complexity of restricted decision and counting constraint satisfaction problems and properties of finite universal algebras, and report some achievements done using the algebraic approach.

Announcement Poster in PDF