Title :
A dichotomy theorem for constraints on a three-element set
Author :
Bulatov, Andrei A.
Author_Institution :
Comput. Lab., Oxford Univ., UK
Abstract :
The Constraint Satisfaction Problem (CSP) provides a common framework for many combinatorial problems. The general CSP is known to be NP-complete; however, certain restrictions on the possible form of constraints may affect the complexity, and lead to tractable problem classes. There is, therefore, a fundamental research direction, aiming to separate those subclasses of the CSP which are tractable, from those which remain NP-complete. In 1978 Schaefer gave an exhaustive solution of this problem for the CSP on a 2-element domain. In this paper we generalise this result to a classification of the complexity of CSPs on a 3-element domain. The main result states that every subclass of the CSP defined by a set of allowed constraints is either tractable or NP-complete, and the criterion separating them is that conjectured by Bulatov et al. (2001). We also exhibit a polynomial time algorithm which, for a given set of allowed constraints, determines whether if this set gives rise to a tractable problem class. To obtain the main result and the algorithm we extensively use the algebraic technique for the CSP developed by Jeavons (1998) and Bulatov et al.
Keywords :
combinatorial mathematics; computational complexity; constraint theory; operations research; set theory; 3-element domain; algebraic technique; combinatorial problems; constraint satisfaction problem; constraints; dichotomy theorem; polynomial time algorithm; subclass; three-element set; tractable problem class; Artificial intelligence; Computational complexity; Computer science; Constraint theory; Laboratories; Linear systems; Machine vision; Polynomials; Processor scheduling; Spatial databases;
Conference_Titel :
Foundations of Computer Science, 2002. Proceedings. The 43rd Annual IEEE Symposium on
Print_ISBN :
0-7695-1822-2
DOI :
10.1109/SFCS.2002.1181990