{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T14:47:53Z","timestamp":1770994073486,"version":"3.50.1"},"reference-count":33,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2022,10,28]],"date-time":"2022-10-28T00:00:00Z","timestamp":1666915200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"European Research Council","award":["771005"],"award-info":[{"award-number":["771005"]}]},{"name":"Russian Foundation for Basic Research","award":["19-01-00200"],"award-info":[{"award-number":["19-01-00200"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2022,10,31]]},"abstract":"<jats:p>We give a surprising classification for the computational complexity of the Quantified Constraint Satisfaction Problem over a constraint language \u0393, QCSP(\u0393), where \u0393 is a finite language over three elements that contains all constants. In particular, such problems are in P, NP-complete, co-NP-complete, or PSpace-complete. Our classification refutes the hitherto widely believed Chen Conjecture.<\/jats:p>\n          <jats:p>\n            Additionally, we show that already on a 4-element domain there exists a constraint language \u0393 such that QCSP(\u0393) is DP-complete (from Boolean Hierarchy), and on a 10-element domain there exists a constraint language giving the complexity class \u0398\n            <jats:sup>P<\/jats:sup>\n            <jats:sub>2<\/jats:sub>\n            .\n          <\/jats:p>\n          <jats:p>\n            Meanwhile, we prove the Chen Conjecture for finite conservative languages \u0393. If the polymorphism clone of such \u0393 has the polynomially generated powers property, then QCSP(\u0393) is in NP. Otherwise, the polymorphism clone of \u0393 has the exponentially generated powers property and QCSP(\u0393) is PSpace-complete.\n            <jats:xref ref-type=\"fn\">\n              <jats:sup>1<\/jats:sup>\n            <\/jats:xref>\n          <\/jats:p>","DOI":"10.1145\/3563820","type":"journal-article","created":{"date-parts":[[2022,9,15]],"date-time":"2022-09-15T09:52:45Z","timestamp":1663235565000},"page":"1-44","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["QCSP Monsters and the Demise of the Chen Conjecture"],"prefix":"10.1145","volume":"69","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0047-5076","authenticated-orcid":false,"given":"Dmitriy","family":"Zhuk","sequence":"first","affiliation":[{"name":"Lomonosov Moscow State University, Russia and Charles University, Prague, Czech Republic"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4642-8614","authenticated-orcid":false,"given":"Barnaby","family":"Martin","sequence":"additional","affiliation":[{"name":"Durham University, South Road, Durham, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,10,28]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11856-017-1621-9"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/2933575.2934544"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10601-008-9054-z"},{"issue":"3","key":"e_1_3_2_5_2","first-page":"2","article-title":"Galois theory for Post algebras parts I and II","volume":"5","author":"Bodnarchuk V. G.","year":"1969","unstructured":"V. G. Bodnarchuk, L. A. Kaluzhnin, V. N. Kotov, and B. A. Romov. 1969. Galois theory for Post algebras parts I and II. Cybernetics 5, 3 (1969), 243\u2013252.","journal-title":"Cybernetics"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2009.05.003"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.117"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700376676"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.37"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(91)90075-D"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2015.50"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.MFCS.2017.27"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30201-8_15"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/1189056.1189076"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1137\/060668572"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00012-011-0125-4"},{"key":"e_1_3_2_17_2","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1007\/978-3-642-29485-3_4","volume-title":"Logic and Program Semantics\u2014Essays Dedicated to Dexter Kozen on the Occasion of His 60th Birthday","author":"Chen Hubie","year":"2012","unstructured":"Hubie Chen. 2012. Meditations on quantified constraint satisfaction. In Logic and Program Semantics\u2014Essays Dedicated to Dexter Kozen on the Occasion of His 60th Birthday. 35\u201349."},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.2168\/LMCS-11(3:9)2015"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CSL.2016.15"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1968.27.95"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1137\/16M1091836"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1093\/logcom\/exw005"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2017.06.023"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1137\/140965715"},{"issue":"3","key":"e_1_3_2_25_2","article-title":"Existence theorems for weakly symmetric operations","volume":"59","author":"Mar\u00f3ti M.","year":"2008","unstructured":"M. Mar\u00f3ti and R. McKenzie. 2008. Existence theorems for weakly symmetric operations. Algebr. Univers. 59, 3 (2008).","journal-title":"Algebr. Univers."},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.4230\/DFU.Vol7.15301.327"},{"key":"e_1_3_2_27_2","volume-title":"Computational Complexity","author":"Papadimitriou Christos H.","year":"1994","unstructured":"Christos H. Papadimitriou. 1994. Computational Complexity. Addison-Wesley."},{"key":"e_1_3_2_28_2","volume-title":"The Two-Valued Iterative Systems of Mathematical Logic","author":"Post E. L.","year":"1941","unstructured":"E. L. Post. 1941. The Two-Valued Iterative Systems of Mathematical Logic. Princeton University Press, Princeton, NJ."},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1145\/800133.804350"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.38"},{"key":"e_1_3_2_31_2","article-title":"A modification of the CSP algorithm for infinite languages","author":"Zhuk Dmitriy","year":"2018","unstructured":"Dmitriy Zhuk. 2018. A modification of the CSP algorithm for infinite languages. arXiv:1803.07465. Retrieved from https:\/\/arxiv.org\/abs\/1803.07165.","journal-title":"arXiv:1803.07465"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcta.2019.04.003"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384232"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01267873"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3563820","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3563820","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:00:07Z","timestamp":1750186807000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3563820"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,10,28]]},"references-count":33,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2022,10,31]]}},"alternative-id":["10.1145\/3563820"],"URL":"https:\/\/doi.org\/10.1145\/3563820","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,10,28]]},"assertion":[{"value":"2020-09-15","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-07-09","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-10-28","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}