{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,10]],"date-time":"2025-12-10T12:49:26Z","timestamp":1765370966144,"version":"3.46.0"},"reference-count":27,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"6","funder":[{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["101071674"],"award-info":[{"award-number":["101071674"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001824","name":"Czech Science Foundation","doi-asserted-by":"crossref","award":["25-16324S"],"award-info":[{"award-number":["25-16324S"]}],"id":[{"id":"10.13039\/501100001824","id-type":"DOI","asserted-by":"crossref"}]},{"name":"European Research Council Executive Agency"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2025,12,31]]},"DOI":"10.1137\/25m1725747","type":"journal-article","created":{"date-parts":[[2025,12,10]],"date-time":"2025-12-10T08:29:36Z","timestamp":1765355376000},"page":"1514-1567","source":"Crossref","is-referenced-by-count":0,"title":["\\(\\boldsymbol{\\Pi_2^P}\\) vs PSpace Dichotomy for the Quantified Constraint Satisfaction Problem"],"prefix":"10.1137","volume":"54","author":[{"given":"Dmitriy","family":"Zhuk","sequence":"first","affiliation":[{"name":"Department of Algebra, Charles University, Prague, 18600 Czech Republic."}]}],"member":"351","published-online":{"date-parts":[[2025,12,10]]},"reference":[{"key":"ref1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804090"},{"key":"ref2","unstructured":"L. Barto, A. Krokhin, and R. Willard, Polymorphisms, and How to Use them, 2017. Preprint."},{"key":"ref3","doi-asserted-by":"crossref","unstructured":"L. Barto and M. Pinsker, The algebraic dichotomy conjecture for infinite domain constraint satisfaction problems, in Proceedings of the 31st Annual ACM\/IEEE Symposium on Logic in Computer Science, LICS \u201916, New York, NY, 2016, pp. 615\u2013622, https:\/\/doi.org\/10.1145\/2933575.2934544.","DOI":"10.1145\/2933575.2934544"},{"key":"ref4","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-09-04874-0"},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2012.03.029"},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2009.05.003"},{"key":"ref7","doi-asserted-by":"crossref","unstructured":"J. Brakensiek and V. Guruswami, Promise constraint satisfaction: Structure theory and a symmetric boolean dichotomy, in Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, New Orleans, LA, 2018, pp. 1782\u20131801, https:\/\/doi.org\/10.1137\/1.9781611975031.117.","DOI":"10.1137\/1.9781611975031.117"},{"key":"ref8","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700376676"},{"key":"ref9","doi-asserted-by":"crossref","unstructured":"A. A. Bulatov, A dichotomy theorem for nonuniform CSPs, in 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), 2017, pp. 319\u2013330.","DOI":"10.1109\/FOCS.2017.37"},{"key":"ref10","unstructured":"A. A. Bulatov, A Dichotomy Theorem for Nonuniform CSPs, CoRR, https:\/\/arxiv.org\/abs\/1703.03021v1, abs\/1703.03021, 2017."},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1145\/1189056.1189076"},{"key":"ref12","doi-asserted-by":"publisher","DOI":"10.1137\/060668572"},{"key":"ref13","doi-asserted-by":"publisher","DOI":"10.1007\/s00012-011-0125-4"},{"key":"ref14","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-29485-3_4"},{"key":"ref15","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(97)00230-2"},{"key":"ref16","doi-asserted-by":"publisher","DOI":"10.1137\/16M1091836"},{"key":"ref17","first-page":"327","volume-title":"Dagstuhl Follow-Ups, Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik 7","author":"Martin B.","year":"2017"},{"key":"ref18","volume-title":"Computational Complexity","author":"Papadimitriou C. H.","year":"1994"},{"key":"ref19","doi-asserted-by":"crossref","unstructured":"T. J. Schaefer, The complexity of satisfiability problems, in Proceedings of the Tenth Annual ACM Symposium on Theory of Computing, STOC \u201978, ACM, 1978, pp. 216\u2013226, https:\/\/doi.org\/10.1145\/800133.804350.","DOI":"10.1145\/800133.804350"},{"key":"ref20","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.38"},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcta.2019.04.003"},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1145\/3402029"},{"key":"ref23","unstructured":"D. Zhuk, The Complexity of the Quantified CSP Having the Polynomially Generated Powers Property, https:\/\/arxiv.org\/abs\/2110.09504, 2021."},{"key":"ref24","doi-asserted-by":"crossref","unstructured":"D. Zhuk, No-rainbow problem and the surjective constraint satisfaction problem, in 2021 36th Annual ACM\/IEEE Symposium on Logic in Computer Science (LICS), IEEE, 2021, pp. 1\u20137.","DOI":"10.1109\/LICS52264.2021.9470632"},{"key":"ref25","first-page":"455","volume":"36","author":"Zhuk D.","year":"2021","journal-title":"J. Multiple-Valued Logic & Soft Comput."},{"key":"ref26","doi-asserted-by":"crossref","unstructured":"D. Zhuk, \\({\\Pi }_{2}^{P}\\) vs PSpace dichotomy for the quantified constraint satisfaction problem, in 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS), IEEE, 2024, pp. 560\u2013572.","DOI":"10.1109\/FOCS61266.2024.00043"},{"key":"ref27","doi-asserted-by":"publisher","DOI":"10.1145\/3563820"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","deposited":{"date-parts":[[2025,12,10]],"date-time":"2025-12-10T08:29:38Z","timestamp":1765355378000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/25M1725747"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,12,10]]},"references-count":27,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2025,12,31]]}},"alternative-id":["10.1137\/25M1725747"],"URL":"https:\/\/doi.org\/10.1137\/25m1725747","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,12,10]]}}}