{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,13]],"date-time":"2026-06-13T20:41:17Z","timestamp":1781383277436,"version":"3.54.1"},"reference-count":19,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2020,6,1]],"date-time":"2020-06-01T00:00:00Z","timestamp":1590969600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF","award":["CCF-1657377"],"award-info":[{"award-number":["CCF-1657377"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2020,9,30]]},"abstract":"<jats:p>The classic TQBF problem is to determine who has a winning strategy in a game played on a given conjunctive normal form formula (CNF), where the two players alternate turns picking truth values for the variables in a given order, and the winner is determined by whether the CNF gets satisfied. We study variants of this game in which the variables may be played in any order, and each turn consists of picking a remaining variable and a truth value for it.<\/jats:p>\n          <jats:p>For the version where the set of variables is partitioned into two halves and each player may only pick variables from his or her half, we prove that the problem is PSPACE-complete for 5-CNFs and in P for 2-CNFs. Previously, it was known to be PSPACE-complete for unbounded-width CNFs (Schaefer, STOC 1976). For the general unordered version (where each variable can be picked by either player), we also prove that the problem is PSPACE-complete for 5-CNFs and in P for 2-CNFs. Previously, it was known to be PSPACE-complete for 6-CNFs (Ahlroth and Orponen, MFCS 2012) and PSPACE-complete for positive 11-CNFs (Schaefer, STOC 1976).<\/jats:p>","DOI":"10.1145\/3397478","type":"journal-article","created":{"date-parts":[[2020,6,1]],"date-time":"2020-06-01T10:13:38Z","timestamp":1591006418000},"page":"1-18","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Complexity of Unordered CNF Games"],"prefix":"10.1145","volume":"12","author":[{"given":"Md Lutfar","family":"Rahman","sequence":"first","affiliation":[{"name":"University of Memphis, Norriswood Ave, Memphis, TN"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Thomas","family":"Watson","sequence":"additional","affiliation":[{"name":"University of Memphis, Norriswood Ave, Memphis, TN"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2020,6]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-32589-2_9"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(02)00491-7"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(79)90002-4"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2016.07.025"},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the 18th Japan Conference on Discrete and Computational Geometry and Graphs (JCDCGG\u201915)","author":"Burke Kyle","year":"2015"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009166"},{"key":"e_1_2_1_8_1","unstructured":"Chris Calabro. 2008. 2-TQBF Is in P. Retrieved May 6 2020 from https:\/\/cseweb.ucsd.edu\/ ccalabro\/essays\/complexity_of_2tqbf.pdf.  Chris Calabro. 2008. 2-TQBF Is in P. Retrieved May 6 2020 from https:\/\/cseweb.ucsd.edu\/ ccalabro\/essays\/complexity_of_2tqbf.pdf."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-48971-0_58"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(87)90074-4"},{"key":"e_1_2_1_11_1","volume-title":"Games of No Chance 3","author":"Hearn Robert"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/800113.803629"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(78)90045-4"},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the 2nd International Conference on Computers and Games (CG\u201900)","author":"Slany Wolfgang","year":"2000"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00179-7"},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the 5th Symposium on Theory of Computing (STOC\u201973)","author":"Stockmeyer Larry","year":"1973"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/0201010"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00235"},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the 25th Benelux Conference on Artificial Intelligence (BNAIC\u201913)","author":"van Rijn Jan","year":"2013"},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the 7th International Conference on Theory and Applications of Satisfiability Testing (SAT\u201904)","author":"Zhao Ling","year":"2004"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3397478","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3397478","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:41:33Z","timestamp":1750200093000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3397478"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6]]},"references-count":19,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2020,9,30]]}},"alternative-id":["10.1145\/3397478"],"URL":"https:\/\/doi.org\/10.1145\/3397478","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"value":"1942-3454","type":"print"},{"value":"1942-3462","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,6]]},"assertion":[{"value":"2019-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-06-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}