{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:13:44Z","timestamp":1750220024103,"version":"3.41.0"},"reference-count":32,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2023,1,18]],"date-time":"2023-01-18T00:00:00Z","timestamp":1674000000000},"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 Trans. Comput. Logic"],"published-print":{"date-parts":[[2023,1,31]]},"abstract":"<jats:p>\n            Let \ud835\udd38 be an idempotent algebra on a finite domain. By mediating between results of Chen [\n            <jats:xref ref-type=\"bibr\">1<\/jats:xref>\n            ] and Zhuk [\n            <jats:xref ref-type=\"bibr\">2<\/jats:xref>\n            ], we argue that if \ud835\udd38 satisfies the polynomially generated powers property (PGP) and \u212c is a constraint language invariant under \ud835\udd38 (i.e., in Inv(\ud835\udd38)), then QCSP \u212c is in NP. In doing this, we study the special forms of PGP, switchability, and collapsibility, in detail, both algebraically and logically, addressing various questions such as decidability on the way.\n          <\/jats:p>\n          <jats:p>\n            We then prove a complexity-theoretic converse in the case of infinite constraint languages encoded in propositional logic, that if Inv}(\ud835\udd38) satisfies the exponentially generated powers property (EGP), then QCSP (Inv(\ud835\udd38)) is co-NP-hard. Since Zhuk proved that only PGP and EGP are possible, we derive a full dichotomy for the QCSP, justifying what we term the\n            <jats:italic>Revised Chen Conjecture<\/jats:italic>\n            . This result becomes more significant now that the original Chen Conjecture (see [\n            <jats:xref ref-type=\"bibr\">3<\/jats:xref>\n            ]) is known to be false [\n            <jats:xref ref-type=\"bibr\">4<\/jats:xref>\n            ].\n          <\/jats:p>\n          <jats:p>\n            Switchability was introduced by Chen [\n            <jats:xref ref-type=\"bibr\">1<\/jats:xref>\n            ] as a generalization of the already-known collapsibility [\n            <jats:xref ref-type=\"bibr\">5<\/jats:xref>\n            ]. There, an algebra \ud835\udd38 :=({ 0,1,2};\n            <jats:italic>r<\/jats:italic>\n            ) was given that is switchable and not collapsible. We prove that, for all finite subsets \u0394 of Inv (\ud835\udd38 A), Pol (\u0394) is collapsible. The significance of this is that, for QCSP on finite structures, it is still possible all QCSP tractability (in NP) explained by switchability is already explained by collapsibility. At least, no counterexample is known to this.\n          <\/jats:p>","DOI":"10.1145\/3568397","type":"journal-article","created":{"date-parts":[[2022,10,17]],"date-time":"2022-10-17T13:09:26Z","timestamp":1666012166000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["The Complexity of Quantified Constraints: Collapsibility, Switchability, and the Algebraic Formulation"],"prefix":"10.1145","volume":"24","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4648-7016","authenticated-orcid":false,"given":"Catarina","family":"Carvalho","sequence":"first","affiliation":[{"name":"University of Hertfordshire, Hatfield, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8528-7105","authenticated-orcid":false,"given":"Florent","family":"Madelaine","sequence":"additional","affiliation":[{"name":"Universit\u00e9 Paris-Est Cr\u00e9teil, Cr\u00e9teil, France"}],"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, Durham, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0047-5076","authenticated-orcid":false,"given":"Dmitriy","family":"Zhuk","sequence":"additional","affiliation":[{"name":"Lomonosov Moscow State University, Moskva, Russia"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,1,18]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00012-011-0125-4"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcta.2019.04.003"},{"key":"e_1_3_2_4_2","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1007\/978-3-642-29485-3_4","volume-title":"Logic and Program Semantics: Essays 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: Essays Dedicated to Dexter Kozen on the Occasion of His 60th Birthday. Lecture Notes in Computer Science, Vol. 7230. Springer, 35\u201349."},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384232"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1137\/060668572"},{"key":"e_1_3_2_7_2","unstructured":"A. Bulatov P. Jeavons and A. Krokhin. 2005. The complexity of constraint satisfaction: An algebraic approach. In Structural Theory of Automata Semigroups and Universal Algebra . NATO Science Series II: Mathematics Physics and Chemistry Vol. 207. Springer 181\u2013213."},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.4230\/DFU.Vol7.15301.1"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.4230\/DFU.Vol7.15301.2"},{"key":"e_1_3_2_10_2","article-title":"On the complexity of the model checking problem","volume":"1210","author":"Madelaine Florent R.","year":"2012","unstructured":"Florent R. Madelaine and Barnaby Martin. 2012. On the complexity of the model checking problem. CoRR abs\/1210.6893 (2012). http:\/\/arxiv.org\/abs\/1210.6893","journal-title":"CoRR"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.37"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.38"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/3402029"},{"key":"e_1_3_2_14_2","first-page":"417","volume-title":"Proceedings of the 17th National Conference on Artificial Intelligence and the 12th Conference on Innovative Applications of Artificial Intelligence","author":"Egly Uwe","year":"2000","unstructured":"Uwe Egly, Thomas Eiter, Hans Tompits, and Stefan Woltran. 2000. Solving advanced reasoning tasks using quantified Boolean formulas. In Proceedings of the 17th National Conference on Artificial Intelligence and the 12th Conference on Innovative Applications of Artificial Intelligence. 417\u2013422."},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1017\/S1446788700028925"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.80"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.MFCS.2017.27"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.5555\/377810"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-007-9083-9"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CSL.2016.15"},{"key":"e_1_3_2_21_2","article-title":"A modification of the CSP algorithm for infinite languages","volume":"1803","author":"Zhuk Dmitriy","year":"2018","unstructured":"Dmitriy Zhuk. 2018. A modification of the CSP algorithm for infinite languages. CoRR abs\/1803.07465 (2018). arxiv:1803.07465","journal-title":"CoRR"},{"key":"e_1_3_2_22_2","volume-title":"Proceedings of the 2015 30th Annual IEEE Symposium on Logic in Computer Science (LICS\u201915)","author":"Carvalho Catarina","year":"2015","unstructured":"Catarina Carvalho, Florent R. Madelaine, and Barnaby Martin. 2015. From complexity to algebra and back: Digraph classes, collapsibility and the PGP. In Proceedings of the 2015 30th Annual IEEE Symposium on Logic in Computer Science (LICS\u201915)."},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2008.15"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-33558-7_36"},{"key":"e_1_3_2_25_2","volume-title":"Proceedings of the 2011 17th International Conference on Principles and Practice of Constraint Programming (CP\u201911).","author":"Martin Barnaby","year":"2011","unstructured":"Barnaby Martin. 2011. QCSP on partially reflexive forests. In Proceedings of the 2011 17th International Conference on Principles and Practice of Constraint Programming (CP\u201911)."},{"key":"e_1_3_2_26_2","doi-asserted-by":"crossref","unstructured":"Barnaby Martin and Florent Madelaine. 2006. Towards a trichotomy for quantified H -coloring. In Logical Approaches to Computational Barriers . Lecture Notes in Computer Science Vol. 3988. Springer 342\u2013352.","DOI":"10.1007\/11780342_36"},{"key":"e_1_3_2_27_2","doi-asserted-by":"crossref","first-page":"311","DOI":"10.1109\/LICS.2011.27","volume-title":"Proceedings of the 2011 26th Annual IEEE Symposium on Logic in Computer Science (LICS\u201911)","author":"Madelaine Florent R.","year":"2011","unstructured":"Florent R. Madelaine and Barnaby Martin. 2011. A tetrachotomy for positive first-order logic without equality. In Proceedings of the 2011 26th Annual IEEE Symposium on Logic in Computer Science (LICS\u201911). 311\u2013320."},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2009.15"},{"key":"e_1_3_2_29_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_30_2","doi-asserted-by":"publisher","DOI":"10.1137\/080725209"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2009.05.003"},{"key":"e_1_3_2_32_2","article-title":"The complexity of quantified constraints","volume":"1701","author":"Carvalho Catarina","year":"2017","unstructured":"Catarina Carvalho, Barnaby Martin, and Dmitriy Zhuk. 2017. The complexity of quantified constraints. CoRR abs\/1701.04086 (2017). arXiv:1701.04086","journal-title":"CoRR"},{"key":"e_1_3_2_33_2","article-title":"The complexity of the quantified CSP having the polynomially generated powers property","author":"Zhuk Dmitriy","year":"2021","unstructured":"Dmitriy Zhuk. 2021. The complexity of the quantified CSP having the polynomially generated powers property. arXiv preprint arXiv:2110.09504 (2021).","journal-title":"arXiv preprint arXiv:2110.09504"}],"container-title":["ACM Transactions on Computational Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3568397","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3568397","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T17:51:33Z","timestamp":1750182693000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3568397"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,1,18]]},"references-count":32,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,1,31]]}},"alternative-id":["10.1145\/3568397"],"URL":"https:\/\/doi.org\/10.1145\/3568397","relation":{},"ISSN":["1529-3785","1557-945X"],"issn-type":[{"type":"print","value":"1529-3785"},{"type":"electronic","value":"1557-945X"}],"subject":[],"published":{"date-parts":[[2023,1,18]]},"assertion":[{"value":"2021-07-14","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-06-24","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-01-18","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}