LIPIcs.SWAT.2022.31.pdf
- Filesize: 0.58 MB
- 11 pages
Document
Erdős-Selfridge Theorem for Nonmonotone CNFs
Authors
-
Part of:
Volume:
18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Scandinavian Symposium and Workshops on Algorithm Theory (SWAT) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2022-06-22
File
Document Identifiers
Acknowledgements
We thank anonymous reviewers for their comments.
Cite AsGet BibTex
Md Lutfar Rahman and Thomas Watson. Erdős-Selfridge Theorem for Nonmonotone CNFs. In 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 227, pp. 31:1-31:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.SWAT.2022.31
https://doi.org/10.4230/LIPIcs.SWAT.2022.31
Abstract
In an influential paper, Erdős and Selfridge introduced the Maker-Breaker game played on a hypergraph, or equivalently, on a monotone CNF. The players take turns assigning values to variables of their choosing, and Breaker’s goal is to satisfy the CNF, while Maker’s goal is to falsify it. The Erdős-Selfridge Theorem says that the least number of clauses in any monotone CNF with k literals per clause where Maker has a winning strategy is Θ(2^k).
We study the analogous question when the CNF is not necessarily monotone. We prove bounds of Θ(√2 ^k) when Maker plays last, and Ω(1.5^k) and O(r^k) when Breaker plays last, where r = (1+√5)/2≈ 1.618 is the golden ratio.
Subject Classification
ACM Subject Classification
- Mathematics of computing → Discrete mathematics
Keywords
- Game
- nonmonotone
- CNFs
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.
-
Jesper Byskov. Maker-Maker and Maker-Breaker games are PSPACE-complete. Technical Report RS-04-14, BRICS, Department of Computer Science, Aarhus University, 2004.
-
Paul Erdős and John Selfridge. On a combinatorial game. Journal of Combinatorial Theory, Series A, 14(3), 1973.
-
Dan Hefetz, Michael Krivelevich, Miloš Stojaković, and Tibor Szabó. Positional Games. Springer, 2014.
-
Martin Kutz. The Angel Problem, Positional Games, and Digraph Roots. PhD thesis, Freie Universität Berlin, 2004. Chapter 2: Weak Positional Games.
-
Martin Kutz. Weak positional games on hypergraphs of rank three. In Proceedings of the 3rd European Conference on Combinatorics, Graph Theory, and Applications (EuroComb), pages 31-36. Discrete Mathematics & Theoretical Computer Science, 2005.
-
Md Lutfar Rahman and Thomas Watson. Complexity of unordered CNF games. ACM Transactions on Computation Theory, 12(3):18:1-18:18, 2020.
-
Md Lutfar Rahman and Thomas Watson. Tractable unordered 3-CNF games. In Proceedings of the 14th Latin American Theoretical Informatics Symposium (LATIN), pages 360-372. Springer, 2020.
-
Md Lutfar Rahman and Thomas Watson. 6-uniform Maker-Breaker game is PSPACE-complete. In Proceedings of the 38th International Symposium on Theoretical Aspects of Computer Science (STACS), pages 57:1-57:15. Schloss Dagstuhl, 2021.
-
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.