THE COMPLEXITY OF CONSTRAINT SATISFACTION PROBLEMS OVER A 3-ELEMENT SET
Dr Andrei Bulatov, Ural State University, Ekaterinburg, Russia

Abstract: The constraint satisfaction problem provides a framework in which it is possible to express, in a natural way, many combinatorial problems. The aim in a constraint satisfaction problem is to find an assignment to a given set of variables subject to certain constraints. A constraint is imposed by specifying certain relations which are required to hold between the values assigned to certain specified subsets of the variables.

The general constraint satisfaction problem is NP-complete, even in the case of a finite set of values. However, for certain sets of relations, the restricted problem in which all the constraints must be members of this given set of relations can be shown to be tractable. In the case of Boolean constraints (that is, constraints over a 2-element set) the tractable cases were completely characterised by Schaefer in 1978, and all intractable cases were proved to be NP-complete. This result is known as Schaefer's Dichotomy Theorem.

By making use of algebraic closure properties of constraints, we generalise the Dichotomy Theorem to the case of a 3-element set of values.

This seminar was held at the Department of Computer Science, Royal Holloway, University of London on 27 June 2001.

back