Programming Research Group
Technical Report TR-4-99
Peter Jeavons
1999, 17 pp.
Abstract
Many natural combinatorial problems can be expressed as constraint satisfaction problems. This class of problems is known to be NP-complete in general, but certain restrictions on the form of the constraints can ensure tractability. In this paper we show that any restricted set of constraint types can be associated with a finite universal algebra. We explore how the computational complexity of a restricted constraint satisfaction problem is connected to properties of the corresponding algebra. For this, we introduce a notion of `tractable algebra' and study how the tractability of an algebra relates to the tractability of its smaller derived algebras, including its subalgebras and homomorphic images. This allows us to significantly reduce the types of algebras which need to be investigated. Using these results we exhibit a common structural property of all known intractable constraint satisfaction problems. Finally, we classify all finite strictly simple surjective algebras with respect to tractability. The result is a dichotomy theorem which significantly generalises Schaefer's dichotomy for the Generalised Satifiability problem.
This paper is available as a 110439 gzipped PostScript file.