LIPIcs.ISAAC.2018.9.pdf
- Filesize: 0.5 MB
- 12 pages
Document
Complexity of Unordered CNF Games
Authors
-
Part of:
Volume:
29th International Symposium on Algorithms and Computation (ISAAC 2018)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Symposium on Algorithms and Computation (ISAAC) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2018-12-06
Cite AsGet BibTex
Md Lutfar Rahman and Thomas Watson. Complexity of Unordered CNF Games. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 9:1-9:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.ISAAC.2018.9
https://doi.org/10.4230/LIPIcs.ISAAC.2018.9
Abstract
The classic TQBF problem is to determine who has a winning strategy in a game played on a given CNF formula, 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.
- For the version where the set of variables is partitioned into two halves and each player may only pick variables from his/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).
Subject Classification
ACM Subject Classification
- Theory of computation → Computational complexity and cryptography
- Theory of computation → Problems, reductions and completeness
- Theory of computation
Keywords
- CNF
- Games
- PSPACE-complete
- SAT
- Linear Time
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
Lauri Ahlroth and Pekka Orponen. Unordered Constraint Satisfaction Games. In Proceedings of the 37th International Symposium on Mathematical Foundations of Computer Science (MFCS), pages 64-75. Springer, 2012.
-
Bengt Aspvall, Michael Plass, and Robert Tarjan. A Linear-Time Algorithm for Testing the Truth of Certain Quantified Boolean Formulas. Information Processing Letters, 8(3):121-123, 1979.
-
Kyle Burke, Erik Demaine, Harrison Gregg, Robert Hearn, Adam Hesterberg, Michael Hoffmann, Hiro Ito, Irina Kostitsyna, Jody Leonard, Maarten Löffler, Aaron Santiago, Christiane Schmidt, Ryuhei Uehara, Yushi Uno, and Aaron Williams. Single-Player and Two-Player Buttons & Scissors Games. In Proceedings of the 18th Japan Conference on Discrete and Computational Geometry and Graphs (JCDCGG), pages 60-72. Springer, 2015.
-
William Burley and Sandy Irani. On Algorithm Design for Metrical Task Systems. Algorithmica, 18(4):461-485, 1997.
-
Jesper Byskov. Maker-Maker and Maker-Breaker Games Are PSPACE-Complete. Technical Report RS-04-14, BRICS, Department of Computer Science, Aarhus University, 2004.
- Chris Calabro. 2-TQBF Is in P, 2008. Unpublished. URL: https://cseweb.ucsd.edu/~ccalabro/essays/complexity_of_2tqbf.pdf.
-
Aviezri Fraenkel and Elisheva Goldschmidt. PSPACE-hardness of some combinatorial games. Journal of Combinatorial Theory, Series A, 46(1):21-38, 1987.
-
Robert Hearn. Amazons, Konane, and Cross Purposes are PSPACE-complete. In Games of No Chance 3, Mathematical Sciences Research Institute Publications, pages 287-306. Cambridge University Press, 2009.
-
Thomas Schaefer. Complexity of Decision Problems Based on Finite Two-Person Perfect-Information Games. In Proceedings of the 8th Symposium on Theory of Computing (STOC), pages 41-49. ACM, 1976.
-
Thomas Schaefer. On the Complexity of Some Two-Person Perfect-Information Games. Journal of Computer and System Sciences, 16(2):185-225, 1978.
-
Larry Stockmeyer and Albert Meyer. Word Problems Requiring Exponential Time. In Proceedings of the 5th Symposium on Theory of Computing (STOC), pages 1-9. ACM, 1973.