ECCC-Report TR02-032https://eccc.weizmann.ac.il/report/2002/032Comments and Revisions published for TR02-032en-usSat, 15 Jun 2002 16:11:56 +0300
Paper TR02-032
| Tractable Constraint Satisfaction Problems on a 3-element set |
Andrei Bulatov
https://eccc.weizmann.ac.il/report/2002/032The 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 a 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, and those which remain NP-complete.
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 is either tractable and the criterion separating them is that conjectured earlier. We also exhibit a polynomial time algorithm which, for a given set of allowed constraints, outputs 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 and coauthors.
Sat, 15 Jun 2002 16:11:56 +0300https://eccc.weizmann.ac.il/report/2002/032