A dichotomy theorem for constraint satisfaction problems on a 3-element set

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 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 that 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 article, we generalise this result to a classification of the complexity of the CSP on a 3-element domain. The main result states that every subproblem of the CSP is either tractable or NP-complete, and the criterion separating them is that conjectured in Bulatov et al. [2005] and Bulatov and Jeavons [2001b]. We also characterize those subproblems for which standard constraint propagation techniques provide a decision procedure. Finally, we 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 in Jeavons [1998b], Bulatov et al.[2005], and Bulatov and Jeavons [2001b].

References

1. Allen, J. 1994. Natural Language Understanding. Benjamin Cummings.]]
2. Bulatov, A. 2002. Mal'tsev constraints are tractable. Tech. Rep. PRG-RR-02-05, Computing Laboratory, University of Oxford, Oxford, UK.]]
3. Bulatov, A. 2006a. Combinatorial problems raised from 2-semilattices. J. Alg., submitted for publication.]]
4. Bulatov, A. 2006b. Three-element Mal'tsev algebras. Acta Sci. Math (Szeged). To appear.]]
5. Bulatov, A., and Jeavons, P. 2000. Tractable constraints closed under a binary operation. Tech. Rep. PRG-TR-12-00, Computing Laboratory, University of Oxford, Oxford, UK.]]
6. Bulatov, A., and Jeavons, P. 2001a. Algebraic approach to multisorted constraints. Tech. Rep. PRG-RR-01-18, Computing Laboratory, University of Oxford, Oxford, UK.]]
7. Bulatov, A., and Jeavons, P. 2001b. Algebraic structures in combinatorial problems. Tech. Rep. MATH-AL-4-2001, Technische universität Dresden, Dresden, Germany.]]
8. Bulatov, A., and Jeavons, P. 2003. An algebraic approach to multisorted constraits. In Proceedings of the 9th International Conference on Principles and Practice of Constraint Programming (CP'03) (Kinsale, Ireland). 197--202.]]
9. Bulatov, A., Jeavons, P., and Krokhin, A. 2001. The complexity of maximal constraint languages. In Proceedings of the 33rd Annual ACM Simposium on Theory of Computing (Hersonissos, Crete, Greece). ACM, New York, 667--674.]]
10. Bulatov, A., Jeavons, P., and Krokhin, A. 2005. Classifying the complexity of constraints using finite algebras. SIAM J. Comput. 34, 720--742.]]
11. Burris, S., and Sankappanavar, H. 1981. A Course in Universal Algebra. Graduate Texts in Mathematics, vol. 78. Springer-Verlag, New York-Berlin.]]
12. Cooper, M. 1989. An optimal k-consistency algorithm. Artif. Intel. 41, 89--95.]]
13. Creignou, N., Khanna, S., and Sudan, M. 2001. Complexity Classifications of Boolean Constraint Satisfaction Problems. SIAM Monographs on Discrete Mathematics and Applications, vol. 7. SIAM, Philadelphia, PA.]]
14. Dalmau, V. 2000. Computational complexity of problems over generalized formulas. Ph.D. dissertation, Department LSI of the Universitat Politecnica de Catalunya (UPC), Barcelona, Spain.]]
15. Dechter, R. 1992. From local to global consistency. Artif. Intel. 55, 1, 87--107.]]
16. Dechter, R. 2003. Constraint processing. Morgan-Kaufmann, San Francisco, CA.]]
17. Dechter, R., and Dechter, A. 1996. Structure-driven algorithms for truth maintenance. Artif. Intel. 82, 1--2, 1--20.]]
18. Dechter, R., and Meiri, I. 1994. Experimental evaluation of preprocessing algorithms for constraint satisfaction problems. Artif. Intel. 68, 211--241.]]
19. Dechter, R., and Pearl, J. 1988. Network-based heuristics for constraint satisfaction problems. Artif. Intel. 34, 1, 1--38.]]
20. Dechter, R., and van Beek, P. 1997. Local and global relational consistency. Theoret. Comput. Sci. 173, 1, 283--308.]]
21. Denecke, K., and Wismath, S. 2002. Universal Algebra and Applications in Theoretical Computer Science. Chapman and Hall/CRC Press.]]
22. Feder, T., and Vardi, M. 1998. The computational structure of monotone monadic SNP and constraint satisfaction: A study through datalog and group theory. SIAM J. Comput. 28, 57--104.]]
23. Freuder, E. 1982. A sufficient condition for backtrack-free search. J. ACM 29, 1, 24--32.]]
24. Gottlob, G., Leone, L., and Scarcello, F. 2000. A comparison of structural CSP decomposition methods. Artif. Intel. 124, 2, 243--282.]]
25. Jeavons, P. 1998a. Constructing constraints. In Proceedings 4th International Conference on Constraint Programming---CP'98 (Pisa, Oct.). Lecture Notes in Computer Science, vol. 1520. Springer-Verlag, New York, 2--16.]]
26. Jeavons, P. 1998b. On the algebraic structure of combinatorial problems. Theoret. Comput. Sci. 200, 185--204.]]
27. Jeavons, P., Cohen, D., and Cooper, M. 1998a. Constraints, consistency and closure. Artif. Intel. 101, 1--2, 251--265.]]
28. Jeavons, P., Cohen, D., and Gyssens, M. 1997. Closure properties of constraints. J. ACM 44, 527--548.]]
29. Jeavons, P., Cohen, D., and Pearson, J. 1998b. Constraints and universal algebra. Ann. Math. Artif. Intel. 24, 51--67.]]
30. Kolaitis, P. 2003. Constraint satisfaction, databases, and logic. In Proceedings of the 17th International Joint Conference on Artificial Intellignece (IJCAI'03).]]
31. Kolaitis, P., and Vardi, M. 2000a. Conjunctive-query containment and constraint satisfaction. J. Comput. Syst. Sci. 61, 302--332.]]
32. Kolaitis, P., and Vardi, M. 2000b. A game-theoretic approach to constraint satisfaction. In Proceedings of the 17th National (US) Conference on Artificial Intelligence (AAAI'00). 175--181.]]
33. Kumar, V. 1992. Algorithms for constraint satisfaction problems: A survey. AI Magazine 13, 1, 32--44.]]
34. Ladner, R. 1975. On the structure of polynomial time reducibility. J. ACM 22, 155--171.]]
35. McKenzie, R., McNulty, G., and Taylor, W. 1987. Algebras, Lattices and Varieties. Vol. I. Wadsworth and Brooks, California.]]
36. Montanari, U. 1974. Networks of constraints: Fundamental properties and applications to picture processing. Inf. Sci. 7, 95--132.]]
37. Nadel, B. 1995. Constraint satisfaction in Prolog: Complexity and theory-based heuristics. Inf. Sci. 83, 3--4, 113--131.]]
38. Nadel, B., and Lin, J. 1991. Automobile transmission design as a constraint satisfaction problem: Modeling the kinematik level. Artif. Intel. Eng. Des. Anal. Manuf. (AI EDAM) 5, 3, 137--171.]]
39. Pöschel, R., and Kalužnin, L. 1979. Funktionen- und Relationenalgebren. DVW, Berlin, Germany.]]
40. Post, E. 1941. The Two-Valued Iterative Systems of Mathematical Logic. Annals Mathematical Studies, vol. 5. Princeton University Press.]]
41. Schaefer, T. 1978. The complexity of satisfiability problems. In Proceedings of the 10th ACM Symposium on Theory of Computing (STOC'78). ACM, New York, 216--226.]]
42. Schwalb, E., and Vila, L. 1998. Temporal constraints: A survey. Constraints 3, 2--3, 129--149.]]
43. Szendrei, A. 1990. Simple surjective algebras having no proper subalgebras. J. Austral. Math. Soc. (Ser. A) 48, 434--454.]]
44. Tsang, E. 1993. Foundations of Constraint Satisfaction. Academic Press, London, England.]]
45. van Hentenryck, P., Deville, Y., and Teng, C.-M. 1992. A generic arc-consistency algorithm and its specializations. Artif. Intel. 57, 291--321.]]
46. Vardi, M. 2000. Constraint satisfaction and database theory: A tutorial. In Proceedings of 19th ACM Symposium on Priciples of Database Systems (PODS'00). ACM, New York.]]

Index Terms

• Mathematics of computing

  • Discrete mathematics

    • Combinatorics

      • Combinatorial algorithms

• Theory of computation

  • Computational complexity and cryptography

    • Problems, reductions and completeness

  • Logic

    • Constraint and logic programming