{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,4]],"date-time":"2026-07-04T05:49:38Z","timestamp":1783144178770,"version":"3.54.6"},"reference-count":58,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2009,12,1]],"date-time":"2009-12-01T00:00:00Z","timestamp":1259625600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Comput. Surv."],"published-print":{"date-parts":[[2009,12]]},"abstract":"<jats:p>An emerging area of research studies the complexity of constraint satisfaction problems under restricted constraint languages. This article gives a self-contained, contemporary presentation of Schaefer's theorem on Boolean constraint satisfaction, the inaugural result of this area, as well as analogs of this theorem for quantified formulas. Our exposition makes use of and may serve as an introduction to logical and algebraic tools that have recently come into focus.<\/jats:p>","DOI":"10.1145\/1592451.1592453","type":"journal-article","created":{"date-parts":[[2009,12,15]],"date-time":"2009-12-15T12:55:54Z","timestamp":1260881754000},"page":"1-32","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":28,"title":["A rendezvous of logic, complexity, and algebra"],"prefix":"10.1145","volume":"42","author":[{"given":"Hubie","family":"Chen","sequence":"first","affiliation":[{"name":"Universitat Pompeu Fabra, Barcelona, Spain"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2009,12,14]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/11549345_8"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(79)90002-4"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2005.31"},{"key":"e_1_2_1_4_1","unstructured":"Bauland M. B\u00f6hler E. Creignou N. Reith S. Schnoor H. and Vollmer H. 2005. Quantified constraints: The complexity of decision and counting for bounded alternation. ECCC Tech. rep. TR05-24. http:\/\/eccc.uni-trier.de\/zear\/2005.  Bauland M. B\u00f6hler E. Creignou N. Reith S. Schnoor H. and Vollmer H. 2005. Quantified constraints: The complexity of decision and counting for bounded alternation. ECCC Tech. rep. TR05-24. http:\/\/eccc.uni-trier.de\/zear\/2005."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-31856-9_9"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/11874683_13"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2007.38"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/11672142_53"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/11753728_14"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01070906"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/954092.954101"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/970831.970840"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the International Conference on Computer Science Logic. Lecture Notes in Computer Science","volume":"2803","author":"B\u00f6rner F.","unstructured":"B\u00f6rner , F. , Bulatov , A. , Krokhin , A. , and Jeavons , P . 2003. Quantified constraints: Algorithms and complexity . In Proceedings of the International Conference on Computer Science Logic. Lecture Notes in Computer Science , vol. 2803 . Springer, Berlin, Germany, 58--70. B\u00f6rner, F., Bulatov, A., Krokhin, A., and Jeavons, P. 2003. Quantified constraints: Algorithms and complexity. In Proceedings of the International Conference on Computer Science Logic. Lecture Notes in Computer Science, vol. 2803. Springer, Berlin, Germany, 58--70."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/788023.789067"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/1018438.1021881"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.09.028"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1120582.1120584"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/050628957"},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of CP.","author":"Bulatov A.","unstructured":"Bulatov , A. and Jeavons , P . 2003. An algebraic approach to multi-sorted constraints . In Proceedings of CP. Bulatov, A. and Jeavons, P. 2003. An algebraic approach to multi-sorted constraints. In Proceedings of CP."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700376676"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1995.1025"},{"key":"e_1_2_1_23_1","doi-asserted-by":"crossref","unstructured":"Burris S. N. and Sankappanavar H. 1981. A Course in Universal Algebra. www.math.uwaterloo.ca\/~snburris\/htclocs\/ualg.html.  Burris S. N. and Sankappanavar H. 1981. A Course in Universal Algebra. www.math.uwaterloo.ca\/~snburris\/htclocs\/ualg.html.","DOI":"10.1007\/978-1-4613-8130-3"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2008.11.001"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/060668572"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/11538363_17"},{"key":"e_1_2_1_27_1","doi-asserted-by":"crossref","unstructured":"Cohen D. and Jeavons P. 2006. The complexity of constraint languages. Handbook of Constraint Programming Chapter 8. Elsevier Amsterdam The Netherlands.  Cohen D. and Jeavons P. 2006. The complexity of constraint languages. Handbook of Constraint Programming Chapter 8. Elsevier Amsterdam The Netherlands.","DOI":"10.1016\/S1574-6526(06)80012-X"},{"key":"e_1_2_1_28_1","doi-asserted-by":"crossref","unstructured":"Creignou N. Khanna S. and Sudan M. 2001. Complexity Classification of Boolean Constraint Satisfaction Problems. SIAM Monographs on Discrete Mathematics and Applications. Society for Industrial and Applied Mathematics Philadelphia PA.   Creignou N. Khanna S. and Sudan M. 2001. Complexity Classification of Boolean Constraint Satisfaction Problems. SIAM Monographs on Discrete Mathematics and Applications. Society for Industrial and Applied Mathematics Philadelphia PA.","DOI":"10.1137\/1.9780898718546"},{"key":"e_1_2_1_29_1","doi-asserted-by":"crossref","unstructured":"Dalmau V. 1997. Some dichotomy theorems on constant-free quantified Boolean formulas. Tech. rep. LSI-97-43-R. Llenguatges i Sistemes Inform\u00e0tics\u2014Universitat Polit\u00e8cnica de Catalunya Barcelona Spain.  Dalmau V. 1997. Some dichotomy theorems on constant-free quantified Boolean formulas. Tech. rep. LSI-97-43-R. Llenguatges i Sistemes Inform\u00e0tics\u2014Universitat Polit\u00e8cnica de Catalunya Barcelona Spain.","DOI":"10.1145\/267460.267496"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2005.19"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.2168\/LMCS-1(1:5)2005"},{"key":"e_1_2_1_33_1","volume-title":"Proceedings of CP. 159--173","author":"Dalmau V.","unstructured":"Dalmau , V. and Pearson , J . 1999. Closure functions and width 1 problems . In Proceedings of CP. 159--173 . Dalmau, V. and Pearson, J. 1999. Closure functions and width 1 problems. In Proceedings of CP. 159--173."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/167088.167245"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794266766"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1968.27.95"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(92)90149-A"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(90)90132-J"},{"key":"e_1_2_1_39_1","unstructured":"Hemaspaandra E. 2004. Dichotomy theorems for alternation-bounded quantified Boolean formulas. eprint. arXiv.cs\/0406006.  Hemaspaandra E. 2004. Dichotomy theorems for alternation-bounded quantified Boolean formulas. eprint. arXiv.cs\/0406006."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(97)00230-2"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(98)00022-8"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/263867.263489"},{"key":"e_1_2_1_43_1","volume-title":"Proceedings of CSL. 129--137","author":"Karpinski M.","unstructured":"Karpinski , M. , B\u00fcning , H. K. , and Schmitt , P. H . 1987. On the computational complexity of quantified horn clauses . In Proceedings of CSL. 129--137 . Karpinski, M., B\u00fcning, H. K., and Schmitt, P. H. 1987. On the computational complexity of quantified horn clauses. In Proceedings of CSL. 129--137."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2006.40"},{"key":"e_1_2_1_45_1","unstructured":"Kl\u00edma O. Tesson P. and Th\u00e9rien D. 2004. Dichotomies in the complexity of solving systems of equations over finite semigroups. ECCC Tech rep. TR04-091. http:\/\/eccc.uni-trier.de\/year\/2004.  Kl\u00edma O. Tesson P. and Th\u00e9rien D. 2004. Dichotomies in the complexity of solving systems of equations over finite semigroups. ECCC Tech rep. TR04-091. http:\/\/eccc.uni-trier.de\/year\/2004."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1147\/rd.254.0327"},{"key":"e_1_2_1_47_1","volume-title":"Proceedings of SMS-NATO ASI. 181--213","author":"Krokhin A.","unstructured":"Krokhin , A. , Bulatov , A. , and Jeavons , P . 2003a. The complexity of constraint satisfaction: An algebraic approach . In Proceedings of SMS-NATO ASI. 181--213 . Krokhin, A., Bulatov, A., and Jeavons, P. 2003a. The complexity of constraint satisfaction: An algebraic approach. In Proceedings of SMS-NATO ASI. 181--213."},{"key":"e_1_2_1_48_1","volume-title":"Proceedings of the 33rd IEEE International Symposium on Multiple-Valued Logic (ISMVL). 343--351","author":"Krokhin A.","unstructured":"Krokhin , A. , Bulatov , A. , and Jeavons , P . 2003b. Functions of multiple-valued logic and the complexity of constraint satisfaction: A short survey . In Proceedings of the 33rd IEEE International Symposium on Multiple-Valued Logic (ISMVL). 343--351 . Krokhin, A., Bulatov, A., and Jeavons, P. 2003b. Functions of multiple-valued logic and the complexity of constraint satisfaction: A short survey. In Proceedings of the 33rd IEEE International Symposium on Multiple-Valued Logic (ISMVL). 343--351."},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2006.6"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00012-007-2012-6"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218196706003116"},{"key":"e_1_2_1_52_1","unstructured":"McKenzie R. McNulty G. and Taylor W. 1987. Algebras Lattices and Varieties. Vol. I. Wadsworth and Brooks\/Cole Belmount CA.  McKenzie R. McNulty G. and Taylor W. 1987. Algebras Lattices and Varieties. Vol. I. Wadsworth and Brooks\/Cole Belmount CA."},{"key":"e_1_2_1_53_1","volume-title":"The Two-Valued Iterative Systems of Mathematical Logic","author":"Post E. L.","unstructured":"Post , E. L. 1941. The Two-Valued Iterative Systems of Mathematical Logic . Princeton University Press , Princeton, NJ . Post, E. L. 1941. The Two-Valued Iterative Systems of Mathematical Logic. Princeton University Press, Princeton, NJ."},{"key":"e_1_2_1_54_1","unstructured":"Reingold O. 2004. Undirected ST-connectivity in log-space. ECCC Tech. rep. TR04-094. http:eccc.uni-trier.de\/year\/2004.  Reingold O. 2004. Undirected ST-connectivity in log-space. ECCC Tech. rep. TR04-094. http:eccc.uni-trier.de\/year\/2004."},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1016\/B978-0-444-87759-8.50029-8"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/800133.804350"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(76)90061-X"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/800125.804029"},{"key":"e_1_2_1_59_1","volume-title":"Clones in Universal Algebra. Seminaires de Mathematiques Superieures","author":"Szendrei A.","unstructured":"Szendrei , A. 1986. Clones in Universal Algebra. Seminaires de Mathematiques Superieures , vol. 99 . University of Montreal , Montreal, P.Q. , Canada. Szendrei, A. 1986. Clones in Universal Algebra. Seminaires de Mathematiques Superieures, vol. 99. University of Montreal, Montreal, P.Q., Canada."},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(76)90062-1"}],"container-title":["ACM Computing Surveys"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1592451.1592453","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1592451.1592453","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T12:17:48Z","timestamp":1750249068000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1592451.1592453"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,12]]},"references-count":58,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2009,12]]}},"alternative-id":["10.1145\/1592451.1592453"],"URL":"https:\/\/doi.org\/10.1145\/1592451.1592453","relation":{},"ISSN":["0360-0300","1557-7341"],"issn-type":[{"value":"0360-0300","type":"print"},{"value":"1557-7341","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,12]]},"assertion":[{"value":"2007-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-12-14","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}