article

The complexity of constraint satisfaction games and QCSP

Authors:

A. KrokhinAuthors Info & Claims

Information and Computation, Volume 207, Issue 9

Pages 923 - 944

https://doi.org/10.1016/j.ic.2009.05.003

Published: 01 September 2009 Publication History

Abstract

We study the complexity of two-person constraint satisfaction games. An instance of such a game is given by a collection of constraints on overlapping sets of variables, and the two players alternately make moves assigning values from a finite domain to the variables, in a specified order. The first player tries to satisfy all constraints, while the other tries to break at least one constraint; the goal is to decide whether the first player has a winning strategy. We show that such games can be conveniently represented by a logical form of quantified constraint satisfaction, where an instance is given by a first-order sentence in which quantifiers alternate and the quantifier-free part is a conjunction of (positive) atomic formulas; the goal is to decide whether the sentence is true. While the problem of deciding such a game is PSPACE-complete in general, by restricting the set of allowed constraint predicates, one can obtain infinite classes of constraint satisfaction games of lower complexity. We use the quantified constraint satisfaction framework to study how the complexity of deciding such a game depends on the parameter set of allowed predicates. With every predicate, one can associate certain predicate-preserving operations, called polymorphisms. We show that the complexity of our games is determined by the surjective polymorphisms of the constraint predicates. We illustrate how this result can be used by identifying the complexity of a wide variety of constraint satisfaction games.

References

[1]

Aspvall, B., Plass, M.F. and Tarjan, R.E., A linear time algorithm for testing the truth of certain quantified Boolean formulas. Information Processing Letters. v8. 121-123.

[2]

Bodlaender, H.L., On the complexity of some coloring games. International Journal of Foundations of Computer Science. v2 i2. 133-147.

[3]

L. Bordeaux, E. Monfroy, Beyond NP: Arc-consistency for quantified constraints, in: Proceedings of CP'02, LNCS, vol. 2470, 2002, pp. 371--386.

[4]

F. B&#246;rner, A. Bulatov, P. Jeavons, A. Krokhin, Quantified constraints: algorithms and complexity, in: Proceedings of CSL'03, LNCS, vol. 2803, 2003, pp. 58--70.

[5]

F. B&#246;rner, A. Krokhin, A. Bulatov, P. Jeavons, Quantified Constraints and Surjective Polymorphisms, Technical Report PRG-RR-02-11, Computing Laboratory, University of Oxford, UK, 2002.

[6]

Bulatov, A., A dichotomy theorem for constraint satisfaction problems on a 3-element set. Journal of the ACM. v53 i1. 66-120.

[7]

A. Bulatov, Tractable conservative constraint satisfaction problems, in: Proceedings of LICS'03, 2003, pp. 321--330.

Digital Library

[8]

A. Bulatov, A graph of a relational structure and constraint satisfaction problems, in: Proceedings of LICS'04, 2004, pp. 448--457.

[9]

Bulatov, A., Combinatorial problems raised from 2-semilattices. Journal of Algebra. v298 i2. 321-339.

[10]

Bulatov, A. and Dalmau, V., A simple algorithm for Mal'tsev constraints. SIAM Journal on Computing. v36 i1. 16-27.

[11]

A. Bulatov, P. Jeavons, An algebraic approach to multi-sorted constraints, in: Proceedings of CP'03, LNCS, vol. 2833, 2003, pp. 183--198.

[12]

Bulatov, A., Jeavons, P. and Krokhin, A., Classifying the complexity of constraints using finite algebras. SIAM Journal on Computing. v34 i3. 720-742.

[13]

Cadoli, M., Schaerf, M., Giovanardi, A. and Giovanardi, M., An algorithm to evaluate quantified Boolean formulae and its experimental evaluation. Journal of Automated Reasoning. v28 i2. 101-142.

[14]

H. Chen, Collapsibility and consistency in quantified constraint satisfaction, in: Proceedings of AAAI'04, 2004, pp. 155--160.

[15]

H. Chen, The Computational Complexity of Quantified Constraint Satisfaction, Ph.D. thesis, Cornell University, 2004.

[16]

H. Chen, Quantified constraint satisfaction and 2-semilattice polymorphisms, in: Proceedings of CP'04, LNCS, vol. 3258, 2004, pp. 168--181.

Digital Library

[17]

H. Chen, Quantified constraint satisfaction, maximal constraint languages, and symmetric polymorphisms, in: Proceedings of STACS'05, LNCS, vol. 3404, 2005, pp. 315--326.

Digital Library

[18]

Chen, H., The complexity of quantified constraint satisfaction: collapsibility, sink algebras, and the three-element case. SIAM Journal on Computing. v37 i5. 1674-1701.

[19]

N. Creignou, S. Khanna, M. Sudan, Complexity classifications of boolean constraint satisfaction problems, SIAM Monographs on Discrete Mathematics and Applications, vol. 7, 2001.

[20]

V. Dalmau, Some dichotomy theorems on constant-free quantified Boolean formulas, Technical Report TR LSI-97-43-R, Department LSI, Universitat Politecnica de Catalunya, 1997.

[21]

V. Dalmau, Constraint satisfaction problems in non-deterministic logarithmic space, in: Proceedings of ICALP'02, LNCS, vol. 2380, 2002, pp. 414--425.

[22]

V. Dalmau, Generalized majority-minority operations are tractable, in: Proceedings of LICS'05, 2005, pp. 438--447.

[23]

Dalmau, V., A new tractable class of constraint satisfaction problems. Annals of Mathematics and Artificial Intelligence. v44 i1--2. 61-85.

[24]

Dechter, R., Constraint Processing. 2003. Morgan Kaufman.

[25]

U. Egly, T. Eiter, H. Tompits, S. Woltran, Solving advanced reasoning tasks using quantified Boolean formulas, in: Proceedings of AAAI'00, 2000, pp. 417--422.

[26]

T. Feder, Ph.G. Kolaitis, Closures and Dichotomies for Quantified Constraints, Electronic Colloquium on Computational Complexity, Report TR06-160, 2006.

[27]

Feder, T. and Vardi, M.Y., The computational structure of monotone monadic SNP and constraint satisfaction: a study through datalog and group theory. SIAM Journal on Computing. v28. 57-104.

[28]

A.S. Fraenkel, Combinatorial games, Electronic Journal of Combinatorics, 2003 (Dynamic Survey DS2).

[29]

Fraenkel, A.S., Complexity, appeal and challenges of combinatorial games. Theoretical Computer Science. v313 i3. 393-415.

[30]

Garey, M. and Johnson, D.S., Computers and Intractability: A Guide to the Theory of NP-Completeness. 1979. Freeman, San Francisco, CA.

[31]

I.A. Gent, P. Nightingale, K. Stergiou, QCSP-solve: a solver for quantified constraint satisfaction problems, in: Proceedings of IJCAI'05, 2005, pp. 138--143.

[32]

Giunchiglia, E., Narizzano, M. and Tacchella, A., Backjumping for quantified Boolean logic satisfiability. Artificial Intelligence. v145 i1--2. 99-120.

[33]

Horn, A., On sentences which are true of direct unions of algebras. Journal of Symbolic Logic. v16 i1. 14-21.

[34]

On the algebraic structure of combinatorial problems. Theoretical Computer Science. v200. 185-204.

[35]

Jeavons, P.G., Cohen, D.A. and Cooper, M.C., Constraints, consistency and closure. Artificial Intelligence. v101 i1--2. 251-265.

[36]

Jeavons, P.G., Cohen, D.A. and Gyssens, M., Closure properties of constraints. Journal of the ACM. v44. 527-548.

[37]

Kleine B&#252;ning, H., Karpinski, M. and Fl&#246;gel, A., Resolution for quantified Boolean formulas. Information and Computation. v117 i1. 12-18.

[38]

Kolaitis, Ph.G. and Vardi, M.Y., Conjunctive-query containment and constraint satisfaction. Journal of Computer and System Sciences. v61. 302-332.

[39]

Ph.G. Kolaitis, M.Y. Vardi, A game-theoretic approach to constraint satisfaction, in: Proceedings of AAAI'00, 2000, pp. 175--181.

[40]

Krokhin, A., Bulatov, A. and Jeavons, P., The complexity of constraint satisfaction: an algebraic approach. In: NATO Science Series II: Math., Phys., Chem, vol. 207. Springer-Verlag. pp. 181-213.

[41]

N. Mamoulis, K. Stergiou, Algorithms for quantified constraint satisfaction problems, in: Proceedings of CP'04, LNCS, vol. 3258, 2004, pp. 752--756.

[42]

B. Martin, F. Madeleine, Towards a trichotomy for quantified H-coloring, in: Proceedings of CiE'06, LNCS, vol. 3988, 2006, pp. 342--352.

Digital Library

[43]

Papadimitriou, C.H., Computational Complexity. 1994. Addison-Wesley.

[44]

Pippenger, N., Theories of Computability. 1997. Cambridge University Press, Cambridge.

[45]

R. P&#246;schel, L.A. Kalu&#382;nin, Funktionen- und Relationenalgebren, DVW, Berlin, 1979.

[46]

Post, E.L., The two-valued iterative systems of mathematical logic. 1941. Annals Mathematical Studies, 1941.Princeton University Press.

[47]

O. Reingold, Undirected ST-connectivity in log-space, in: Proceedings of STOC'05, 2005, pp. 376--385.

Digital Library

[48]

Rintanen, J., Constructing conditional plans by a theorem-prover. Journal of Artificial Intelligence Research. v10. 323-352.

[49]

M. Rychlik, On probabilistic quantified satisfiability games, in: Proceedings of MFCS'03, LNCS, vol. 2747, 2003, pp. 652--661.

[50]

T.J. Schaefer, The complexity of satisfiability problems, in: Proceedings of STOC'78, 1978, pp. 216--226.

[51]

Schaefer, T.J., On the complexity of some two-person perfect-information games. Journal of Computer and System Sciences. v16 i2. 185-225.

[52]

A. Szendrei, Clones in Universal Algebra, Seminaires de Mathematiques Superieures, vol. 99, University of Montreal, 1986.

[53]

R. Williams, Algorithms for quantified Boolean formulas, in: Proceedings of SODA'02, 2002, pp. 299--307.

Cited By

Zhuk DMartin B(2022)QCSP Monsters and the Demise of the Chen ConjectureJournal of the ACM10.1145/356382069:5(1-44)Online publication date: 15-Sep-2022
https://dl.acm.org/doi/10.1145/3563820
Barto LBrady ZBulatov AKozik MZhuk DGorla D(2021)Minimal taylor algebras as a common framework for the three algebraic approaches to the CSPProceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science10.1109/LICS52264.2021.9470557(1-13)Online publication date: 29-Jun-2021
https://dl.acm.org/doi/10.1109/LICS52264.2021.9470557
Zhuk D(2020)A Proof of the CSP Dichotomy ConjectureJournal of the ACM10.1145/340202967:5(1-78)Online publication date: 26-Aug-2020
https://dl.acm.org/doi/10.1145/3402029
Show More Cited By

Index Terms

The complexity of constraint satisfaction games and QCSP
1. Theory of computation
  1. Design and analysis of algorithms
  2. Logic
    1. Constraint and logic programming

Recommendations

The complexity of temporal constraint satisfaction problems
STOC '08: Proceedings of the fortieth annual ACM symposium on Theory of computing

A temporal constraint language is a set of relations that has a first-order definition in (b Q,<), the dense linear order of the rational numbers. We present a complete complexity classification of the constraint satisfaction problem (CSP) for temporal ...
A pre-processing algorithm for solving constraint satisfaction optimisation problems
SAICSIT '03: Proceedings of the 2003 annual research conference of the South African institute of computer scientists and information technologists on Enablement through technology

A constraint satisfaction problem (CSP) involves finding values, selected from a finite domain, for all variables such that all constraints on the variables are satisfied. A constraint satisfaction optimisation problem (CSOP) is a CSP that has some ...
Constraint satisfaction with succinctly specified relations

The general intractability of the constraint satisfaction problem (CSP) has motivated the study of the complexity of restricted cases of this problem. Thus far, the literature has primarily considered the formulation of the CSP where constraint ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Information and Computation

Information and Computation Volume 207, Issue 9

September, 2009

61 pages

ISSN:0890-5401

Issue’s Table of Contents

Copyright © © 2009.

Publisher

Academic Press, Inc.

United States

Publication History

Published: 01 September 2009

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

16
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 13 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Zhuk DMartin B(2022)QCSP Monsters and the Demise of the Chen ConjectureJournal of the ACM10.1145/356382069:5(1-44)Online publication date: 15-Sep-2022
https://dl.acm.org/doi/10.1145/3563820
Barto LBrady ZBulatov AKozik MZhuk DGorla D(2021)Minimal taylor algebras as a common framework for the three algebraic approaches to the CSPProceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science10.1109/LICS52264.2021.9470557(1-13)Online publication date: 29-Jun-2021
https://dl.acm.org/doi/10.1109/LICS52264.2021.9470557
Zhuk D(2020)A Proof of the CSP Dichotomy ConjectureJournal of the ACM10.1145/340202967:5(1-78)Online publication date: 26-Aug-2020
https://dl.acm.org/doi/10.1145/3402029
Zhuk DMartin BMakarychev KMakarychev YTulsiani MKamath GChuzhoy J(2020)QCSP monsters and the demise of the chen conjectureProceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing10.1145/3357713.3384232(91-104)Online publication date: 22-Jun-2020
https://dl.acm.org/doi/10.1145/3357713.3384232
Chen HLarose B(2017)Asking the Metaquestions in Constraint TractabilityACM Transactions on Computation Theory10.1145/31347579:3(1-27)Online publication date: 4-Oct-2017
https://dl.acm.org/doi/10.1145/3134757
Đapić PMarković PMartin B(2017)Quantified Constraint Satisfaction Problem on Semicomplete DigraphsACM Transactions on Computational Logic10.1145/300789918:1(1-47)Online publication date: 13-Apr-2017
https://dl.acm.org/doi/10.1145/3007899
(2016)Complexity of the game domination problemTheoretical Computer Science10.1016/j.tcs.2016.07.025648:C(1-7)Online publication date: 4-Oct-2016
https://dl.acm.org/doi/10.1016/j.tcs.2016.07.025
Bova SGanian RSzeider S(2016)Quantified conjunctive queries on partially ordered setsTheoretical Computer Science10.1016/j.tcs.2016.01.010618:C(72-84)Online publication date: 7-Mar-2016
https://dl.acm.org/doi/10.1016/j.tcs.2016.01.010
Carvalho CMadelaine FMartin B(2015)From Complexity to Algebra and BackProceedings of the 2015 30th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)10.1109/LICS.2015.50(462-474)Online publication date: 6-Jul-2015
https://dl.acm.org/doi/10.1109/LICS.2015.50
Bova SChen H(2015)The complexity of equivalence, entailment, and minimization in existential positive logicJournal of Computer and System Sciences10.1016/j.jcss.2014.10.00281:2(443-457)Online publication date: 1-Mar-2015
https://dl.acm.org/doi/10.1016/j.jcss.2014.10.002
Show More Cited By

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents