{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,3]],"date-time":"2025-12-03T17:03:59Z","timestamp":1764781439110,"version":"3.46.0"},"reference-count":0,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2025,9,22]],"date-time":"2025-09-22T00:00:00Z","timestamp":1758499200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,9,22]],"date-time":"2025-09-22T00:00:00Z","timestamp":1758499200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["comput. complex."],"published-print":{"date-parts":[[2025,12]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    The classic TQBF problem can be viewed as a game in which two players alternate turns assigning truth values to a \nCNF formula's variables in a prescribed order, and the winner is determined by whether the \nCNF gets satisfied. The complexity of deciding which player has a winning strategy in this game is well-understood: it is \n-complete for 2-CNFs and -complete for 3-CNFs. We continue the \nstudy of the\n                    <jats:italic>unordered<\/jats:italic>\n                    variant of this game, in which each turn consists of picking \nany remaining variable and assigning it a truth value. The complexity of deciding who can win on a given CNF is less well-understood; prior work by the authors showed it is in \n for 2-CNFs and -complete for 5-CNFs. We conjecture it may be efficiently \nsolvable on 3-CNFs, and we make progress in this direction by proving the problem is \nin , indeed in , for 3-CNFs with a certain restriction, namely that each \nwidth-3 clause has at least one variable that appears in no other clause. Another (incomparable) \nrestriction of this problem was previously shown to be tractable by Kutz.\n                  <\/jats:p>","DOI":"10.1007\/s00037-025-00274-7","type":"journal-article","created":{"date-parts":[[2025,9,22]],"date-time":"2025-09-22T12:07:59Z","timestamp":1758542879000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Tractable Unordered 3-CNF Games"],"prefix":"10.1007","volume":"34","author":[{"given":"Md Lutfar","family":"Rahman","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Thomas","family":"Watson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,9,22]]},"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-025-00274-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00037-025-00274-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-025-00274-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,3]],"date-time":"2025-12-03T16:59:58Z","timestamp":1764781198000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00037-025-00274-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,9,22]]},"references-count":0,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,12]]}},"alternative-id":["274"],"URL":"https:\/\/doi.org\/10.1007\/s00037-025-00274-7","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"type":"print","value":"1016-3328"},{"type":"electronic","value":"1420-8954"}],"subject":[],"published":{"date-parts":[[2025,9,22]]},"assertion":[{"value":"22 January 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 August 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 September 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"12"}}