Quantified Constraint Satisfaction, Maximal Constraint Languages, and Symmetric Polymorphisms | SpringerLink
Skip to main content
Springer Nature Link
Log in

Quantified Constraint Satisfaction, Maximal Constraint Languages, and Symmetric Polymorphisms

  • Conference paper
STACS 2005 (STACS 2005)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 3404))

Included in the following conference series:

Abstract

The constraint satisfaction problem (CSP) is a convenient framework for modelling search problems; the CSP involves deciding, given a set of constraints on variables, whether or not there is an assignment to the variables satisfying all of the constraints. This paper is concerned with the quantified constraint satisfaction problem (QCSP), a more general framework in which variables can be quantified both universally and existentially. We study the complexity of restricted cases of the QCSP where the types of constraints that may appear are restricted by a constraint language. We give a complete complexity classification of maximal constraint languages, the largest possible languages that can be tractable. We also give a complete complexity classification of constraint languages arising from symmetric polymorphisms.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Aspvall, B., Plass, M.F., Tarjan, R.E.: A linear-time algorithm for testing the truth of certain quantified boolean formulas. Information Processing Letters 8(3), 121–123 (1979)

    Article  MATH  MathSciNet  Google Scholar 

  2. Böhler, E., Creignou, N., Reith, S., Vollmer, H.: Playing with boolean blocks, part II: constraint satisfaction problems. ACM SIGACT-Newsletter 35(1), 22–35 (2004)

    Article  Google Scholar 

  3. Börner, F., Bulatov, A., Krokhin, A., Jeavons, P.: Quantified constraints: Algorithms and complexity. In: Computer Science Logic 2003 (2003)

    Google Scholar 

  4. Bulatov, A.: Combinatorial problems raised from 2-semilattices (manuscript)

    Google Scholar 

  5. Bulatov, A.: A dichotomy theorem for constraints on a three-element set. In: Proceedings of 43rd IEEE Symposium on Foundations of Computer Science, pp. 649–658 (2002)

    Google Scholar 

  6. Bulatov, A.: Malt’sev constraints are tractable. Technical Report PRG-RR-02-05, Oxford University (2002)

    Google Scholar 

  7. Bulatov, A.: Tractable conservative constraint satisfaction problems. In: Proceedings of 18th IEEE Symposium on Logic in Computer Science (LICS 2003), pp. 321–330 (2003)

    Google Scholar 

  8. Bulatov, A.: A graph of a relational structure and constraint satisfaction problems. In: Proceedings of 19th IEEE Annual Symposium on Logic in Computer Science (LICS 2004) (2004)

    Google Scholar 

  9. Bulatov, A., Jeavons, P.: Tractable constraints closed under a binary operation. Technical Report PRG-TR-12-00, Oxford University (2000)

    Google Scholar 

  10. Bulatov, A., Krokhin, A., Jeavons, P.: Constraint satisfaction problems and finite algebras. In: Welzl, E., Montanari, U., Rolim, J.D.P. (eds.) ICALP 2000. LNCS, vol. 1853, pp. 272–282. Springer, Heidelberg (2000)

    Chapter  Google Scholar 

  11. Bulatov, A., Krokhin, A., Jeavons, P.: The complexity of maximal constraint languages. In: ACM Symposium on Theory of Computing, pp. 667–674 (2001)

    Google Scholar 

  12. Büning, H.K., Karpinski, M., Flögel, A.: Resolution for quantified boolean formulas. Information and Computation 117(1), 12–18 (1995)

    Article  MATH  MathSciNet  Google Scholar 

  13. Chen, H.: Collapsibility and consistency in quantified constraint satisfaction. In: AAAI (2004)

    Google Scholar 

  14. Chen, H.: Quantified constraint satisfaction and 2-semilattice polymorphisms. In: Wallace, M. (ed.) CP 2004. LNCS, vol. 3258, pp. 168–181. Springer, Heidelberg (2004)

    Chapter  Google Scholar 

  15. Creignou, N., Khanna, S., Sudan, M.: Complexity Classification of Boolean Constraint Satisfaction Problems, Society for Industrial and Applied Mathematics. SIAM Monographs on Discrete Mathematics and Applications (2001)

    Google Scholar 

  16. Dalmau, V.: Some dichotomy theorems on constant-free quantified boolean formulas. Technical Report LSI-97-43-R, Llenguatges i Sistemes Informàtics - Universitat Politècnica de Catalunya (1997)

    Google Scholar 

  17. Dalmau, V.: A new tractable class of constraint satisfaction problems. In: 6th International Symposium on Artificial Intelligence and Mathematics (2000)

    Google Scholar 

  18. Dalmau, V., Pearson, J.: Closure functions and width 1 problems. In: Jaffar, J. (ed.) CP 1999. LNCS, vol. 1713, pp. 159–173. Springer, Heidelberg (1999)

    Google Scholar 

  19. Feder, T., Vardi, M.Y.: The computational structure of monotone monadic snp and constraint satisfaction: A study through datalog and group theory. SIAM J. Comput. 28(1), 57–104 (1998)

    Article  MATH  MathSciNet  Google Scholar 

  20. Jeavons, P.: On the algebraic structure of combinatorial problems. Theoretical Computer Science 200, 185–204 (1998)

    Article  MATH  MathSciNet  Google Scholar 

  21. Jeavons, P., Cohen, D., Cooper, M.: Constraints, consistency, and closure. Articial Intelligence 101(1-2), 251–265 (1998)

    Article  MATH  MathSciNet  Google Scholar 

  22. Jeavons, P., Cohen, D., Pearson, J.: Constraints and universal algebra. Annals of Mathematics and Artificial Intelligence 24(1-4), 51–67 (1998)

    Article  MATH  MathSciNet  Google Scholar 

  23. Jeavons, P.G., Cohen, D.A., Gyssens, M.: Closure properties of constraints. Journal of the ACM 44, 527–548 (1997)

    Article  MATH  MathSciNet  Google Scholar 

  24. Kavvadias, D., Sideri, M.: The inverse satisfiability problem. SIAM Journal on Computing 28(1), 152–163 (1998)

    Article  MATH  MathSciNet  Google Scholar 

  25. Khanna, S., Sudan, M., Trevisan, L., Williamson, D.P.: The approximability of constraint satisfaction problems. SIAM Journal on Computing 30(6), 1863–1920 (2001)

    Article  MATH  MathSciNet  Google Scholar 

  26. Kirousis, L.M., Kolaitis, P.G.: The complexity of minimal satisfiability problems. In: Ferreira, A., Reichel, H. (eds.) STACS 2001. LNCS, vol. 2010, pp. 407–418. Springer, Heidelberg (2001)

    Chapter  Google Scholar 

  27. Kolaitis, Ph.G., Vardi, M.Y.: Conjunctive-query containment and constraint satisfaction. Journal of Computer and System Sciences 61, 302–332 (2000)

    Article  MATH  MathSciNet  Google Scholar 

  28. Post, E.L.: The Two-Valued Iterative Systems of Mathematical Logic. Princeton University Press, Princeton (1941)

    MATH  Google Scholar 

  29. Rosenberg, I.G.: Minimal clones I: the five types. In: Lectures in Universal Algebra (Proc. Conf. Szeged 1983). Colloq. Math. Soc. Janos Bolyai, vol. 43, pp. 405–427. North-Holland, Amsterdam (1986)

    Google Scholar 

  30. Schaefer, T.J.: The complexity of satisfiability problems. In: Proceedings of the ACM Symposium on Theory of Computing (STOC), pp. 216–226 (1978)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Departament de Tecnologia, Universitat Pompeu Fabra, Barcelona, Spain

    Hubie Chen

Authors
  1. Hubie Chen
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Universität Stuttgart, FMI, Germany

    Volker Diekert

  2. LIF, CNRS & Univ. de Provence,, Marseille

    Bruno Durand

Rights and permissions

Reprints and permissions

Copyright information

© 2005 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Chen, H. (2005). Quantified Constraint Satisfaction, Maximal Constraint Languages, and Symmetric Polymorphisms. In: Diekert, V., Durand, B. (eds) STACS 2005. STACS 2005. Lecture Notes in Computer Science, vol 3404. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-31856-9_26

Download citation

  • DOI: https://doi.org/10.1007/978-3-540-31856-9_26

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-24998-6

  • Online ISBN: 978-3-540-31856-9

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics