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 $$\varvec{\Theta (2^k)}$$ Θ ( 2 k ) . We study the analogous question when the CNF is not necessarily monotone. We prove bounds of $$\varvec{\Theta (\sqrt{2}\,^k)}$$ Θ ( 2 k ) when Maker plays last, and $$\varvec{\Omega (1.5^k)}$$ Ω ( 1 . 5 k ) and $$\varvec{O(r^k)}$$ O ( r k ) when Breaker plays last, where $$\varvec{r=(1+\sqrt{5})/2\approx 1.618}$$ r = ( 1 + 5 ) / 2 ≈ 1.618 is the golden ratio.

Abstract The classic TQBF problem can be viewed as a game in which two players alternate turns assigning truth values to a CNF formula's variables in a prescribed order, and the winner is determined by whether the CNF gets satisfied. The complexity of deciding which player has a winning strategy in this game is well-understood: it is -complete for 2-CNFs and -complete for 3-CNFs. We continue the study of the unordered variant of this game, in which each turn consists of picking any 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 for 2-CNFs and -complete for 5-CNFs. We conjecture it may be efficiently solvable on 3-CNFs, and we make progress in this direction by proving the problem is in , indeed in , for 3-CNFs with a certain restriction, namely that each width-3 clause has at least one variable that appears in no other clause. Another (incomparable) restriction of this problem was previously shown to be tractable by Kutz.

In a STOC 1976 paper, Schaefer proved that it is PSPACE-complete to determine the winner of the so-called Maker-Breaker game on a given set system, even when every set has size at most 11. Since then, there has been no improvement on this result. We prove that the game remains PSPACE-complete even when every set has size 6.