Erdős–Selfridge Theorem for Nonmonotone CNFs

Md Lutfar Rahman Thomas Watson
University of Memphis

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 $\Theta(2^{k})$ .

We study the analogous question when the CNF is not necessarily monotone. We prove bounds of $\Theta(\sqrt{2}\thinspace^{k})$ when Maker plays last, and $\Omega(1.5^{k})$ and $O(r^{k})$ when Breaker plays last, where $r=(1+\sqrt{5})/2\approx 1.618$ is the golden ratio.

1 Introduction

In 1973, Erdős and Selfridge published a paper [ES73] with several fundamental contributions, including:

Being widely regarded as the genesis of the method of conditional expectations. The subsequent impact of this method on theoretical computer science needs no explanation.
Introducing the so-called Maker-Breaker game, variants of which have since been studied in numerous papers in the combinatorics literature.

We revisit that seminal work and steer it in a new direction. The main theorem from [ES73] can be phrased in terms of CNFs (conjunctive normal form boolean formulas) that are monotone (they contain only positive literals). We investigate what happens for general CNFs, which may contain negative literals. We feel that the influence of Erdős–Selfridge and the pervasiveness of CNFs in theoretical computer science justify this question as inherently worthy of attention. Our pursuit of the answer uncovers new techniques and invites the development of further techniques to achieve a full resolution in the future.

In the Maker-Breaker game played on a monotone CNF, the eponymous players take turns assigning boolean values to variables of their choosing. Breaker wins if the CNF gets satisfied, and Maker wins otherwise; there are no draws. Since the CNF is monotone, Breaker might as well assign $1$ to every variable she picks, and Maker might as well assign $0$ to every variable he picks. In the generalization to nonmonotone CNFs, each player can pick which remaining variable and which bit to assign it during their turn. To distinguish this general game, we rename Breaker as T (for “true”) and Maker as F (for “false”). The computational complexity of deciding which player has a winning strategy has been studied in [Sch76, Sch78, Bys04, Kut04, Kut05, AO12, RW20a, RW20b, RW21].

A CNF is $k$ -uniform when every clause has exactly $k$ literals (corresponding to $k$ distinct variables). The Erdős–Selfridge Theorem answers an extremal question: How few clauses can there be in a $k$ -uniform monotone CNF that Maker can win? It depends a little on which player gets the opening move: $2^{k}$ if Breaker plays first, and $2^{k-1}$ if Maker plays first. The identity of the player with the final move doesn’t affect the answer for monotone CNFs. In contrast, “who gets the last laugh” matters a lot for general CNFs:

Theorem 1 (informal).

If F plays last, then the least number of clauses in any $k$ -uniform CNF where F has a winning strategy is $\Theta(\sqrt{2}\thinspace^{k})$ .

Theorem 2 (informal).

If T plays last, then the least number of clauses in any $k$ -uniform CNF where F has a winning strategy is $\Omega(1.5^{k})$ and $O(r^{k})$ where $r=(1+\sqrt{5})/2\approx 1.618$ .

The most involved proof is the $\Omega(1.5^{k})$ lower bound in Theorem 2. We conjecture the correct bound is $\Theta(r^{k})$ .

2 Results

In the unordered CNF game, there is a CNF $\varphi$ and a set of variables $X$ containing all variables that appear in $\varphi$ and possibly more. The players T and F alternate turns; each turn consists of picking an unassigned variable from $X$ and picking a value $0$ or $1$ to assign it.¹¹1This game is called “unordered” to contrast it with the related TQBF game, in which the variables must be played in a prescribed order. The game ends when all variables are assigned; T wins if $\varphi$ is satisfied (every clause has a true literal), and F wins if $\varphi$ is unsatisfied (some clause has all false literals). There are four possible patterns according to “who goes first” and “who goes last.” If the same player has the first and last moves, then $|X|$ is odd, and if different players have the first and last moves, then $|X|$ is even.

Definition 1.

For $k\geq 0$ and $a,b\in\{\text{T},\text{F}\}$ , we let $M_{k,a\cdots b}$ be the minimum number of clauses in $\varphi$ , over all unordered CNF game instances $(\varphi,X)$ where $\varphi$ is $k$ -uniform and F has a winning strategy when player $a$ has the first move and player $b$ has the last move.

Theorem 1 (formal).

$M_{k,\text{T}\cdots\text{F}}=\sqrt{2}\thinspace^{k}$ for even $k$ , and $1.5\sqrt{2}\thinspace^{k-1}\leq M_{k,\text{T}\cdots\text{F}}\leq\sqrt{2}\thinspace^{k+1}$ for odd $k$ .

Let $\text{Fib}_{k}$ denote the $k^{\text{th}}$ Fibonacci number. It is well-known that $\text{Fib}_{k}=\Theta(r^{k})$ where $r=(1+\sqrt{5})/2\approx 1.618$ .

Theorem 2 (formal).

$1.5^{k}\leq M_{k,\text{T}\cdots\text{T}}\leq\text{Fib}_{k+2}$ for all $k$ .

Observation 1.

$M_{k,\text{F}\cdots b}=M_{k-1,\text{T}\cdots b}$ for all $k\geq 1$ and $b\in\{\text{T},\text{F}\}$ .

Proof.

$M_{k,\text{F}\cdots b}\leq M_{k-1,\text{T}\cdots b}$ : Suppose F wins $(\varphi,X)$ when T moves first, where $\varphi$ is $(k-1)$ -uniform. Then F wins $(\varphi^{\prime},X\cup\{x_{0}\})$ when F moves first, where $x_{0}$ is a fresh variable (not already in $X$ ) and $\varphi^{\prime}$ is the same as $\varphi$ but with $x_{0}$ added to each clause. F’s winning strategy is to play $x_{0}=0$ first and then use the winning strategy for $(\varphi,X)$ . Note that $\varphi^{\prime}$ is $k$ -uniform and has the same number of clauses as $\varphi$ .

$M_{k-1,\text{T}\cdots b}\leq M_{k,\text{F}\cdots b}$ : Suppose F wins $(\varphi,X)$ when F moves first, where $\varphi$ is $k$ -uniform. Say the opening move in F’s winning strategy is $\ell_{i}=1$ , where $\ell_{i}\in\{x_{i},\overline{x}_{i}\}$ is some literal. Obtain $\varphi^{\prime}$ from $\varphi$ by removing each clause containing $\ell_{i}$ , removing $\overline{\ell}_{i}$ from each clause containing $\overline{\ell}_{i}$ , and removing an arbitrary literal from each clause containing neither $\ell_{i}$ nor $\overline{\ell}_{i}$ . Then F wins $(\varphi^{\prime},X-\{x_{i}\})$ when T moves first, and $\varphi^{\prime}$ is $(k-1)$ -uniform and has at most as many clauses as $\varphi$ .

Corollary 1.

$M_{k,\text{F}\cdots\text{F}}=\sqrt{2}\thinspace^{k-1}$ for odd $k$ , and $1.5\sqrt{2}\thinspace^{k-2}\leq M_{k,\text{F}\cdots\text{F}}\leq\sqrt{2}\thinspace^{k}$ for even $k$ .
$1.5^{k-1}\leq M_{k,\text{F}\cdots\text{T}}\leq\text{Fib}_{k+1}$ for all $k$ .

(Observation 1 requires $k\geq 1$ , but the bounds in Corollary 1 also hold for $k=0$ since $M_{0,a\cdots b}=1$ .)

3 Upper bounds

In this section, we prove the upper bounds of Theorem 1 and Theorem 2 by giving examples of game instances with few clauses where F wins. In [ES73], Erdős and Selfridge proved the upper bound for the Maker-Breaker game by showing a $k$ -uniform monotone CNF with $2^{k}$ clauses where Maker (F) wins. The basic idea is that F can win on the following formula, which is not a CNF:

(x_{1}\land x_{2})\lor(x_{3}\land x_{4})\lor\cdots\lor(x_{2k-1}\land x_{2k})

Whenever T plays a variable, F responds by assigning $0$ to the paired variable. By the distributive law, this expands to a $k$ -uniform monotone CNF with $2^{k}$ clauses. We study nonmonotone CNFs, which may have both positive and negative literals.

3.1 F plays last

Lemma 1.

$M_{k,\text{T}\cdots\text{F}}\leq\sqrt{2}\thinspace^{k}$ for even $k$ .

Proof.

F can win on the following formula, which is not a CNF, with variables $X_{k}=\{x_{1},\ldots,x_{k}\}$ .

(x_{1}\oplus x_{2})\lor(x_{3}\oplus x_{4})\lor\cdots\lor(x_{k-1}\oplus x_{k})

Whenever T plays a variable, F responds by playing the paired variable to make them equal. To convert this formula to an equivalent CNF, first replace each $(x_{i}\oplus x_{i+1})$ with $(x_{i}\lor x_{i+1})\land(\overline{x}_{i}\lor\overline{x}_{i+1})$ . Then by the distributive law, this expands to a $k$ -uniform CNF $\varphi_{k}$ where one clause is

((x_{1}\lor x_{2})\lor(x_{3}\lor x_{4})\lor\cdots\lor(x_{k-1}\lor x_{k}))

and for $i\in\{1,3,5,\ldots,k-1\}$ , each clause contains either $(x_{i}\lor x_{i+1})$ or $(\overline{x}_{i}\lor\overline{x}_{i+1})$ . Therefore $\varphi_{k}$ has $2^{k/2}=\sqrt{2}\thinspace^{k}$ clauses: one clause for each $S\subseteq\{1,3,5,\ldots,k-1\}$ . F wins in $(\varphi_{k},X_{k})$ .

Lemma 2.

$M_{k,\text{T}\cdots\text{F}}\leq\sqrt{2}\thinspace^{k+1}$ for odd $k$ .

Proof.

Suppose $\varphi_{k-1}$ is the $(k-1)$ -uniform CNF with $\sqrt{2}\thinspace^{k-1}$ clauses from Lemma 1 (since $k-1$ is even). We take two copies of $\varphi_{k-1}$ , and put a new variable $x_{k}$ in each clause of one copy, and a new variable $x_{k+1}$ in each clause of the other copy. Call this $\varphi_{k}$ . Formally:

	$\displaystyle\varphi_{k}=\bigwedge\limits_{C\in\varphi_{k-1}}(C\lor x_{k})\land(C\lor x_{k+1})$
	$\displaystyle X_{k}=\{x_{1},x_{2},\ldots,x_{k+1}\}$

We argue F wins in $(\varphi_{k},X_{k})$ . If T plays $x_{k}$ or $x_{k+1}$ , F responds by assigning $0$ to the other one. For other variables, F follows his winning strategy for $(\varphi_{k-1},X_{k-1})$ from Lemma 1. Since $\varphi_{k-1}$ is a $(k-1)$ -uniform CNF with $\sqrt{2}\thinspace^{k-1}$ clauses, $\varphi_{k}$ is a $k$ -uniform CNF with $2\sqrt{2}\thinspace^{k-1}=\sqrt{2}\thinspace^{k+1}$ clauses.

3.2 T plays last

Before proving Lemma 3 we draw an intuition. We already know that F wins on

(x_{1}\land x_{2})\lor(x_{3}\land x_{4})\lor\cdots\lor(x_{2k-1}\land x_{2k}).

Now replace each $(x_{i}\land x_{i+1})$ with $(x_{i}\land(\overline{x}_{i}\lor x_{i+1}))$ , which is equivalent. This does not change the function expressed by the formula, so F still wins this T $\cdots$ F game. To turn it into a T $\cdots$ T game, we can introduce a dummy variable $x_{0}$ . Since the game is equivalent to a monotone game, neither player has any incentive to play $x_{0}$ , so F still wins this T $\cdots$ T game.

If we convert it to a CNF, then by the distributive law it will again have $2^{k}$ clauses. But this CNF is not uniform—each clause has at least $k$ literals and at most $2k$ literals. We can do a similar construction that balances the CNF to make it uniform. This intuitively suggests that $\sqrt{2}\thinspace^{k}<M_{k,\text{T}\cdots\text{T}}<2^{k}$ .

Lemma 3.

$M_{k,\text{T}\cdots\text{T}}\leq\text{Fib}_{k+2}$ .

Proof.

For every $k\in\{0,1,2,\ldots\}$ we recursively define a $k$ -uniform CNF $\varphi_{k}$ on variables $X_{k}$ , where $X_{k}=\{x_{0},x_{1},\ldots,x_{2k-2}\}$ if $k>0$ , and $X_{0}=\{x_{0}\}$ (these $\varphi_{k}$ , $X_{k}$ are different than in Section 3.1):

$k=0$ : $\varphi_{0}=()$
$k=1$ : $\varphi_{1}=(x_{0})\land(\overline{x}_{0})$
$k>1$ : $\varphi_{k}=\bigwedge\limits_{C\in\varphi_{k-1}}(C\lor x_{2k-3})\land\bigwedge\limits_{C\in\varphi_{k-2}}(C\lor\overline{x}_{2k-3}\lor x_{2k-2})$

Now we argue F wins in $(\varphi_{k},X_{k})$ . F’s strategy is to assign $0$ to at least one variable from each pair $\{x_{1},x_{2}\},\{x_{3},x_{4}\},\{x_{5},x_{6}\},\ldots,\{x_{2k-3},x_{2k-2}\}$ . Whenever T plays from a pair, F responds by assigning $0$ to the other variable. After T plays $x_{0}$ , F picks a fresh pair $\{x_{i},x_{i+1}\}$ where $i$ is odd and assigns one of them $0$ , then “chases” T until T plays the other from $\{x_{i},x_{i+1}\}$ . Here the “chase” means whenever T plays from a fresh pair, F responds by assigning $0$ to the other variable in that pair. After T returns to $\{x_{i},x_{i+1}\}$ , then F picks another fresh pair to start another chase, and so on in phases. We prove by induction on $k$ that this strategy ensures $\varphi_{k}$ is unsatisfied:

$k=0$ : $\varphi_{0}$ is obviously unsatisfied.
$k=1$ : $\varphi_{1}$ is obviously unsatisfied.
$k>1$ : By induction, both $\varphi_{k-1}$ and $\varphi_{k-2}$ are unsatisfied. Now $\varphi_{k}$ is unsatisfied since: By F’s strategy, at least one of $\{x_{2k-3},x_{2k-2}\}$ is assigned $0$ . If $x_{2k-3}=0$ then one of the clauses of $\varphi_{k}$ that came from $\varphi_{k-1}$ is unsatisfied. If $x_{2k-3}=1$ and $x_{2k-2}=0$ then one of the clauses of $\varphi_{k}$ that came from $\varphi_{k-2}$ is unsatisfied.

Letting $|\varphi_{k}|$ represent the number of clauses in $\varphi_{k}$ , we argue $|\varphi_{k}|=\text{Fib}_{k+2}$ by induction on $k$ :

$k=0$ : $|\varphi_{0}|=1=\text{Fib}_{2}$ .
$k=1$ : $|\varphi_{1}|=2=\text{Fib}_{3}$ .
$k>1$ : By induction, $|\varphi_{k-1}|=\text{Fib}_{k+1}$ and $|\varphi_{k-2}|=\text{Fib}_{k}$ . So

$|\varphi_{k}|=|\varphi_{k-1}|+|\varphi_{k-2}|=\text{Fib}_{k+1}+\text{Fib}_{k}=\text{Fib}_{k+2}.$

Therefore $M_{k,\text{T}\cdots\text{T}}\leq\text{Fib}_{k+2}$ .

4 Lower bounds

4.1 Notation

In the proofs, we will define a potential value $p(C)$ for each clause $C$ . The value of $p(C)$ depends on the context. If $\varphi$ is a CNF (any set of clauses), then the potential of $\varphi$ is $p(\varphi)=\sum_{C\in\varphi}p(C)$ . The potential of a literal $\ell_{i}$ with respect to $\varphi$ is defined as $p(\varphi,\ell_{i})=p(\{C\in\varphi:\ell_{i}\in C\})$ . When we have a particular $\varphi$ in mind, we can abbreviate $p(\varphi,\ell_{i})$ as $p(\ell_{i})$ .

Suppose $\varphi$ is a CNF and $\ell_{i},\ell_{j}$ are two literals. We define the potentials of different sets of clauses based on which of $\ell_{i},\ell_{j}$ , and their complements exist in the clause. For example, $a(\varphi,\ell_{i},\ell_{j})$ is the sum of the potentials of clauses in $\varphi$ that contain both $\ell_{i},\ell_{j}$ .

	$\ell_{j}$	$\overline{\ell}_{j}$	neither $\ell_{j}$ nor $\overline{\ell}_{j}$
$\ell_{i}$	$a$	$b$	$c$
$\overline{\ell}_{i}$	$d$	$e$	$f$
neither $\ell_{i}$ nor $\overline{\ell}_{i}$	$g$	$h$

	$\displaystyle a(\varphi,\ell_{i},\ell_{j})~{}$	$\displaystyle=~{}p(\{C\in\varphi:\ell_{i}\in C~{}\text{and}~{}\ell_{j}\in C\})$
	$\displaystyle b(\varphi,\ell_{i},\ell_{j})~{}$	$\displaystyle=~{}p(\{C\in\varphi:\ell_{i}\in C~{}\text{and}~{}\overline{\ell}_{j}\in C\})$
	$\displaystyle c(\varphi,\ell_{i},\ell_{j})~{}$	$\displaystyle=~{}p(\{C\in\varphi:\ell_{i}\in C~{}\text{and}~{}\ell_{j}\notin C~{}\text{and}~{}\overline{\ell}_{j}\notin C\})$
	$\displaystyle d(\varphi,\ell_{i},\ell_{j})~{}$	$\displaystyle=~{}p(\{C\in\varphi:\overline{\ell}_{i}\in C~{}\text{and}~{}\ell_{j}\in C\})$
	$\displaystyle e(\varphi,\ell_{i},\ell_{j})~{}$	$\displaystyle=~{}p(\{C\in\varphi:\overline{\ell}_{i}\in C~{}\text{and}~{}\overline{\ell}_{j}\in C\})$
	$\displaystyle f(\varphi,\ell_{i},\ell_{j})~{}$	$\displaystyle=~{}p(\{C\in\varphi:\overline{\ell}_{i}\in C~{}\text{and}~{}\ell_{j}\notin C~{}\text{and}~{}\overline{\ell}_{j}\notin C\})$
	$\displaystyle g(\varphi,\ell_{i},\ell_{j})~{}$	$\displaystyle=~{}p(\{C\in\varphi:\ell_{i}\notin C~{}\text{and}~{}\overline{\ell}_{i}\notin C~{}\text{and}~{}\ell_{j}\in C\})$
	$\displaystyle h(\varphi,\ell_{i},\ell_{j})~{}$	$\displaystyle=~{}p(\{C\in\varphi:\ell_{i}\notin C~{}\text{and}~{}\overline{\ell}_{i}\notin C~{}\text{and}~{}\overline{\ell}_{j}\in C\})$

We can abbreviate these quantities as $a,b,c,d,e,f,g,h$ in contexts where we have particular $\varphi,\ell_{i},\ell_{j}$ in mind. Also the following relations hold:

	$\displaystyle p(\ell_{i})~{}$	$\displaystyle=~{}a+b+c$
	$\displaystyle p(\overline{\ell}_{i})~{}$	$\displaystyle=~{}d+e+f$
	$\displaystyle p(\ell_{j})~{}$	$\displaystyle=~{}a+d+g$
	$\displaystyle p(\overline{\ell}_{j})~{}$	$\displaystyle=~{}b+e+h$

When we assign $\ell_{i}=1$ (i.e., assign $x_{i}=1$ if $\ell_{i}$ is $x_{i}$ , or assign $x_{i}=0$ if $\ell_{i}$ is $\overline{x}_{i}$ ), $\varphi$ becomes the residual CNF denoted $\varphi[\ell_{i}=1]$ where all clauses containing $\ell_{i}$ get removed, and the literal $\overline{\ell}_{i}$ gets removed from remaining clauses.

4.2 F plays last

Lemma 4.

$M_{k,\text{T}\cdots\text{F}}\geq\sqrt{2}\thinspace^{k}$ for even $k$ .

Proof.

Consider any $\text{T}\cdots\text{F}$ game instance $(\varphi,X)$ where $\varphi$ is a $k$ -uniform CNF with $<\sqrt{2}\thinspace^{k}$ clauses and $|X|$ is even. We show T has a winning strategy. In this proof, we use $p(C)=1/\sqrt{2}\thinspace^{|C|}$ . A round consists of a T move followed by an F move.

Claim 1.

In every round, there exists a move for T such that for every response by F, we have $p(\psi)\geq p(\psi^{\prime})$ where $\psi$ is the residual CNF before the round and $\psi^{\prime}$ is the residual CNF after the round.

At the beginning we have $p(C)=1/\sqrt{2}\thinspace^{k}$ for each clause $C\in\varphi$ , so $p(\varphi)<\sqrt{2}\thinspace^{k}/\sqrt{2}\thinspace^{k}=1$ . By Claim 1, T has a strategy guaranteeing that $p(\psi)\leq p(\varphi)<1$ where $\psi$ is the residual CNF after all variables have been played. If this final $\psi$ contained a clause, the clause would be empty and have potential $1/\sqrt{2}\thinspace^{0}=1$ , which would imply $p(\psi)\geq 1$ . Thus the final $\psi$ must have no clauses, which means $\varphi$ got satisfied and T won. This concludes the proof of Lemma 4, except for the proof of Claim 1.

Proof of Claim 1.

Let $\psi$ be the residual CNF at the beginning of a round. T picks a literal $\ell_{i}$ maximizing $p(\psi,\ell_{i})$ and plays $\ell_{i}=1$ .²²2It is perhaps counterintuitive that T’s strategy ignores the effect of clauses that contain $\overline{\ell}_{i}$ , which increase in potential after playing $\ell_{i}=1$ . A more intuitive strategy would be to pick a literal $\ell_{i}$ maximizing $p(\psi,\ell_{i})-(\sqrt{2}-1)p(\psi,\overline{\ell}_{i})$ , which is the overall decrease in potential from playing $\ell_{i}=1$ ; this strategy also works but is trickier to analyze. Suppose F responds by playing $\ell_{j}=1$ , and let $\psi^{\prime}$ be the residual CNF after F’s move. Letting the $a,b,c,d,e,f,g,h$ notation be with respect to $\psi,\ell_{i},\ell_{j}$ , we have

p(\psi)-p(\psi^{\prime})=a+b+c+d+g-\bigl{(}e+(\sqrt{2}-1)(f+h)\bigr{)}

because:

Clauses from the $a,b,c,d,g$ groups are satisfied and removed (since they contain $\ell_{i}=1$ or $\ell_{j}=1$ or both), so their potential gets multiplied by $0$ .
Clauses from the $e$ group each shrink by two literals (since they contain $\overline{\ell}_{i}=0$ and $\overline{\ell}_{j}=0$ ), so their potential gets multiplied by $\sqrt{2}\cdot\sqrt{2}=2$ .
Clauses from the $f,h$ groups each shrink by one literal, so their potential gets multiplied by $\sqrt{2}$ .

By the choice of $\ell_{i}$ , we have $p(\ell_{i})\geq p(\overline{\ell}_{i})$ and $p(\ell_{i})\geq p(\overline{\ell}_{j})$ with respect to $\psi$ , in other words, $a+b+c\geq d+e+f$ and $a+b+c\geq b+e+h$ . Thus $p(\psi)\geq p(\psi^{\prime})$ because

	$\displaystyle a+b+c+d+g~{}\geq~{}a+b+c~{}\textstyle\geq~{}\frac{1}{2}(d+e+f)+\frac{1}{2}(b+e+h)$	$\displaystyle~{}\textstyle\geq~{}e+\frac{1}{2}(f+h)$
		$\displaystyle~{}\geq~{}e+(\sqrt{2}-1)(f+h).$

Note: It did not matter whether $k$ is even or odd! Lemma 4 is true for any $k$ . Lemma 5 actually uses oddness of $k$ . The main idea is to exploit the slack $1/2\geq\sqrt{2}-1$ that appeared at the end of the proof of Claim 1.

Lemma 5.

$M_{k,\text{T}\cdots\text{F}}\geq 1.5\thinspace\sqrt{2}\thinspace^{k-1}$ for odd $k$ .

Proof.

Consider any $\text{T}\cdots\text{F}$ game instance $(\varphi,X)$ where $\varphi$ is a $k$ -uniform CNF with $<1.5\thinspace\sqrt{2}\thinspace^{k-1}$ clauses and $|X|$ is even. We show T has a winning strategy. In this proof, we use

\displaystyle p(C)=\begin{cases}1/\sqrt{2}\thinspace^{|C|}&\text{if $|C|$ is even}.\\ 1/1.5\sqrt{2}\thinspace^{|C|-1}&\text{if $|C|$ is odd}.\end{cases}

Claim 2.

At the beginning we have $p(C)=1/1.5\sqrt{2}\thinspace^{k-1}$ for each clause $C\in\varphi$ (since $|C|=k$ , which is odd), so $p(\varphi)<1.5\thinspace\sqrt{2}\thinspace^{k-1}/1.5\thinspace\sqrt{2}\thinspace^{k-1}=1$ . By Claim 2, T has a strategy guaranteeing that $p(\psi)\leq p(\varphi)<1$ where $\psi$ is the residual CNF after all variables have been played. If this final $\psi$ contained a clause, the clause would be empty and have potential $1/\sqrt{2}\thinspace^{0}=1$ (since $0$ is even), which would imply $p(\psi)\geq 1$ . Thus the final $\psi$ must have no clauses, which means $\varphi$ got satisfied and T won. This concludes the proof of Lemma 5, except for the proof of Claim 2.

Proof of Claim 2.

Let $\psi$ be the residual CNF at the beginning of a round. T picks a literal $\ell_{i}$ maximizing $p(\psi,\ell_{i})$ and plays $\ell_{i}=1$ . Suppose F responds by playing $\ell_{j}=1$ , and let $\psi^{\prime}$ be the residual CNF after F’s move. Letting the $a,b,c,d,e,f,g,h$ notation be with respect to $\psi,\ell_{i},\ell_{j}$ , we have

p(\psi)-p(\psi^{\prime})\geq a+b+c+d+g-\bigl{(}e+\textstyle{\frac{1}{2}}(f+h)\bigr{)}

because:

Clauses from the $a,b,c,d,g$ groups are satisfied and removed (since they contain $\ell_{i}=1$ or $\ell_{j}=1$ or both), so their potential gets multiplied by $0$ .
Clauses from the $e$ group each shrink by two literals (since they contain $\overline{\ell}_{i}=0$ and $\overline{\ell}_{j}=0$ ). Here odd-width clauses remain odd and even-width clauses remain even, so their potential gets multiplied by $\sqrt{2}\cdot\sqrt{2}=2$ .
Clauses from the $f,h$ groups each shrink by one literal. There are two cases for a clause $C$ in these groups:
- $|C|$ is even, so $p(C)=1/\sqrt{2}\thinspace^{|C|}$ . After $C$ being shrunk by 1, the new clause $C^{\prime}$ has potential $p(C^{\prime})=1/1.5\sqrt{2}\thinspace^{|C^{\prime}|-1}=1/1.5\sqrt{2}\thinspace^{|C|-2}$ . So the potential of an even-width clause gets multiplied by $p(C^{\prime})/p(C)=4/3$ .
- $|C|$ is odd, so $p(C)=1/1.5\sqrt{2}\thinspace^{|C|-1}$ . After $C$ being shrunk by 1, the new clause $C^{\prime}$ has potential $p(C^{\prime})=1/\sqrt{2}\thinspace^{|C^{\prime}|}=1/\sqrt{2}\thinspace^{|C|-1}$ . So the potential of an odd-width clause gets multiplied by $p(C^{\prime})/p(C)=3/2$ .
So their potential gets multiplied by $\leq 3/2$ (since $4/3\leq 3/2$ ).

\textstyle a+b+c+d+g~{}\geq~{}a+b+c~{}\geq~{}\frac{1}{2}(d+e+f)+\frac{1}{2}(b+e+h)~{}\geq~{}e+\frac{1}{2}(f+h).

4.3 T plays last

Lemma 6.

$M_{k,\text{T}\cdots\text{T}}\geq 1.5\thinspace^{k}$ .

Proof.

Consider any $\text{T}\cdots\text{T}$ game instance $(\varphi,X)$ where $\varphi$ is a $k$ -uniform CNF with $<1.5^{k}$ clauses and $|X|$ is odd. We show T has a winning strategy. In this proof, we use $p(C)=1/1.5^{|C|}$ .

For intuition, how can T take advantage of having the last move? She will look out for certain pairs of literals to “set aside” and wait for F to assign one of them, and then respond by assigning the other one the opposite value. We call such a pair “zugzwang,” which means a situation where F’s obligation to make a move is a disadvantage for F. Upon finding such a pair, T anticipates that certain clauses will get satisfied later, but other clauses containing those literals might shrink when the zugzwang pair eventually gets played. Thus T can update the CNF to pretend those events have already transpired. The normal gameplay of TF rounds (T plays, then F plays) will sometimes get interrupted by FT rounds of playing previously-designated zugzwang pairs. We define the zugzwang condition so that T’s modifications won’t increase the potential of the CNF (which is no longer simply a residual version of $\varphi$ ). When there are no remaining zugzwang pairs to set aside, we can exploit this fact—together with T’s choice of “best” literal for her normal move—to analyze the potential change in a TF round. This allows the proof to handle a smaller potential function and hence more initial clauses, compared to when F had the last move.

initialize

\psi\leftarrow\varphi

;

Y\leftarrow X

;

\zeta\leftarrow\{\}

;

Z\leftarrow\{\}

while game is not over do

while FindZugzwang() returns a pair (

\ell_{i},\ell_{j}

) do

TfoundZugzwang(

\ell_{i},\ell_{j}

)

TplayNormal()

while F picks

x_{k}\in Z

and

\ell_{k}\in\{x_{k},\overline{x}_{k}\}

and assigns

\ell_{k}=1

TplayZugzwang(

\ell_{k}

)

|Y\cup Z|=0

then halt

FplayNormal()

subroutine FindZugzwang():

if there exist distinct

x_{i},x_{j}\in Y

and

\ell_{i}\in\{x_{i},\overline{x}_{i}\}

and

\ell_{j}\in\{x_{j},\overline{x}_{j}\}

such that (with respect to

\psi,\ell_{i},\ell_{j}

\textstyle a+e\geq\frac{5}{4}(b+d)+\frac{1}{2}(c+f+g+h)

then return

(\ell_{i},\ell_{j})

return NULL

subroutine TfoundZugzwang( $\ell_{i},\ell_{j}$ ):

/* T modifies

\psi

with the intention to make

\ell_{i}\neq\ell_{j}

by waiting for F to touch

\{x_{i},x_{j}\}

\zeta\leftarrow\zeta\cup\{(\ell_{i}\oplus\ell_{j})\}

;

Z\leftarrow Z\cup\{x_{i},x_{j}\}

;

Y\leftarrow Y-\{x_{i},x_{j}\}

remove from

\psi

every clause containing

\ell_{i}\lor\ell_{j}

or containing

\overline{\ell}_{i}\lor\overline{\ell}_{j}

remove

\ell_{i},\overline{\ell}_{i},\ell_{j},\overline{\ell}_{j}

from all other clauses of

\psi

subroutine TplayZugzwang( $\ell_{k}$ ):

/* T makes

\ell_{m}\neq\ell_{k}

T picks

x_{m}\in Z

and

\ell_{m}\in\{x_{m},\overline{x}_{m}\}

such that

(\ell_{k}\oplus\ell_{m})\in\zeta

and assigns

\ell_{m}=0

\zeta\leftarrow\zeta-\{(\ell_{k}\oplus\ell_{m})\}

;

Z\leftarrow Z-\{x_{k},x_{m}\}

subroutine TplayNormal():

T picks

x_{i}\in Y

and

\ell_{i}\in\{x_{i},\overline{x}_{i}\}

maximizing

p(\psi,\ell_{i})-p(\psi,\overline{\ell}_{i})

and assigns

\ell_{i}=1

\psi\leftarrow\psi[\ell_{i}=1]

;

Y\leftarrow Y-\{x_{i}\}

subroutine FplayNormal():

F picks

x_{j}\in Y

and

\ell_{j}\in\{x_{j},\overline{x}_{j}\}

and assigns

\ell_{j}=1

\psi\leftarrow\psi[\ell_{j}=1]

;

Y\leftarrow Y-\{x_{j}\}

;

Algorithm 1 T’s winning strategy in

(\varphi,X)

We describe T’s winning strategy in $(\varphi,X)$ as Algorithm 1. In the first line, the algorithm declares and initializes $\psi,Y,\zeta,Z$ , which are accessed globally. Here $\psi$ is a CNF (initially the same as $\varphi$ ), and $\zeta$ is a set (conjunction) of constraints of the form $(\ell_{i}\oplus\ell_{j})$ . We consider $(\ell_{i}\oplus\ell_{j})$ , $(\ell_{j}\oplus\ell_{i})$ , $(\overline{\ell}_{i}\oplus\overline{\ell}_{j})$ , $(\overline{\ell}_{j}\oplus\overline{\ell}_{i})$ to be the same constraint as each other. The algorithm maintains the following three invariants:

(1)

$Y$ and $Z$ are disjoint subsets of $X$ , and $Y\cup Z$ is the set of unplayed variables, and $Y$ contains all variables that appear in $\psi$ , and $Z$ is exactly the set of variables that appear in $\zeta$ , and $|Z|$ is even.
(2)

For every assignment to $Y\cup Z$ , if $\psi$ and $\zeta$ are satisfied, then $\varphi$ is also satisfied by the same assignment together with the assignment played by T and F so far to the other variables of $X$ .
(3)

$p(\psi)<1$ .

Now we argue how these invariants are maintained at the end of the outer loop in Algorithm 1. Invariant (1) is straightforward to see.

Claim 3.

Invariant $(2)$ is maintained.

Proof.

Invariant (2) trivially holds at the beginning.

Each iteration of the first inner loop maintains (2): Say $\psi$ and $\zeta$ are at the beginning of the iteration, and $\psi^{\prime}$ and $\zeta^{\prime}$ denote the formulas after the iteration. Assume (2) holds for $\psi$ and $\zeta$ . To see that (2) holds for $\psi^{\prime}$ and $\zeta^{\prime}$ , consider any assignment to the unplayed variables. We will argue that if $\psi^{\prime}$ and $\zeta^{\prime}$ are satisfied, then $\psi$ and $\zeta$ are satisfied, which implies (by assumption) that $\varphi$ is satisfied. So suppose $\psi^{\prime}$ and $\zeta^{\prime}$ are satisfied. Then $\psi$ is satisfied because each clause containing $\ell_{i}\lor\ell_{j}$ or containing $\overline{\ell}_{i}\lor\overline{\ell}_{j}$ is satisfied due to $(\ell_{i}\oplus\ell_{j})$ being satisfied in $\zeta^{\prime}$ , and each other clause is satisfied since it contains the corresponding clause in $\psi^{\prime}$ which is satisfied. Also, $\zeta$ is satisfied since each of its constraints is also in $\zeta^{\prime}$ which is satisfied.

It is immediate that T’s and F’s “normal” moves in the outer loop maintain (2), because of the way we update $\psi$ and $Y$ .

Each iteration of the second inner loop maintains (2): If an assignment satisfies $\psi^{\prime}$ and $\zeta^{\prime}$ (after the iteration) then it also satisfies $\psi$ and $\zeta$ (at the beginning of the iteration) since T’s move satisfies $(\ell_{k}\oplus\ell_{m})$ —and therefore the assignment satisfies $\varphi$ .

Claim 4.

Invariant $(3)$ is maintained.

Proof.

Invariant (3) holds at the beginning by the assumption that $\varphi$ has $<1.5^{k}$ clauses (and each clause has potential $1/1.5^{k}$ ).

The first inner loop maintains (3) by the following proposition, which we prove later.

Proposition 1.

If FindZugzwang() returns $(\ell_{i},\ell_{j})$ , then $p(\psi)\geq p(\psi^{\prime})$ where $\psi$ and $\psi^{\prime}$ are the CNFs before and after the execution of TfoundZugzwang().

The second inner loop does not affect (3). In each outer iteration except the last, T’s and F’s moves from $Y$ maintain (3) by the following proposition, which we prove later.

Proposition 2.

If FindZugzwang() returns NULL, then $p(\psi)\geq p(\psi^{\prime})$ where $\psi$ is the CNF before TplayNormal() and $\psi^{\prime}$ is the CNF after FplayNormal().

This concludes the proof of Claim 4.

Now we argue why T wins in the last outer iteration. Right before TplayNormal(), $|Y|$ must be odd by invariant (1), because an even number of variables have been played so far (since T has the first move) and $|X|$ is odd (since T also has the last move) and $|Z|$ is even. Thus, T always has an available move in TplayNormal() since $|Y|>0$ at this point. When T is about to play the last variable $x_{i}\in Y$ (possibly followed by some $Z$ moves in the second inner loop), all remaining clauses in $\psi$ have width $\leq 1$ . There cannot be an empty clause in $\psi$ , because then $p(\psi)$ would be $\geq 1/1.5^{0}=1$ , contradicting invariant (3). There cannot be more than one clause in $\psi$ , because then $p(\psi)$ would be $\geq 2/1.5^{1}\geq 1$ . Thus $\psi$ is either empty (already satisfied) or just $(x_{i})$ or just $(\overline{x}_{i})$ , which T satisfies in one move.

At termination, $Y$ and $Z$ are empty, and $\psi$ and $\zeta$ are empty and thus satisfied. By invariant (2), this means $\varphi$ is satisfied by the gameplay, so T wins.

This concludes the proof of Lemma 6 except Proposition 1 and Proposition 2.

Proof of Proposition 1.

Since FindZugzwang() returns $(\ell_{i},\ell_{j})$ , the following holds with respect to $\psi,\ell_{i},\ell_{j}$ :

\textstyle a+e\geq\frac{5}{4}(b+d)+\frac{1}{2}(c+f+g+h)

(

\spadesuit

)

We also have

\textstyle p(\psi)-p(\psi^{\prime})=a+e-\bigl{(}\frac{5}{4}(b+d)+\frac{1}{2}(c+f+g+h)\bigr{)}

because:

Clauses from the $a,e$ groups are removed (since they contain $\ell_{i}\lor\ell_{j}$ or $\overline{\ell}_{i}\lor\overline{\ell}_{j}$ ), so their potential gets multiplied by $0$ . (Intuitively, T considers these clauses satisfied in advance since she will satisfy $(\ell_{i}\oplus\ell_{j})$ later.)
Clauses from the $b,d$ groups each shrink by two literals (since they contain two of $\ell_{i},\overline{\ell}_{i},\ell_{j},\overline{\ell}_{j}$ which are removed), so their potential gets multiplied by $1.5\cdot 1.5=9/4$ . (Some of these four literals will eventually get assigned $1$ , but since T cannot predict which ones, she pessimistically assumes they are all $0$ .)
Clauses from the $c,f,g,h$ groups each shrink by one literal (since they contain one of $\ell_{i},\overline{\ell}_{i},\ell_{j},\overline{\ell}_{j}$ which are removed), so their potential gets multiplied by $1.5=3/2$ .

Since (missing) $\spadesuit$ holds, $p(\psi)\geq p(\psi^{\prime})$ .

Proof of Proposition 2.

In TplayNormal(), T picks the literal $\ell_{i}$ maximizing $p(\psi,\ell_{i})-p(\psi,\overline{\ell}_{i})$ and plays $\ell_{i}=1$ .³³3Some other strategies would also work here, but this one is the simplest to analyze. In FplayNormal(), F plays $\ell_{j}=1$ . With respect to $\psi,\ell_{i},\ell_{j}$ we have

\textstyle p(\psi)-p(\psi^{\prime})=a+b+c+d+g-\bigl{(}\frac{5}{4}e+\frac{1}{2}(f+h)\bigr{)}

because:

Clauses from the $a,b,c,d,g$ groups are satisfied and removed (since they contain $\ell_{i}=1$ or $\ell_{j}=1$ or both), so their potential gets multiplied by $0$ .
Clauses from the $e$ group each shrink by two literals (since they contain $\overline{\ell}_{i}=0$ and $\overline{\ell}_{j}=0$ ), so their potential gets multiplied by $1.5\cdot 1.5=9/4$ .
Clauses from the $f,h$ groups each shrink by one literal, so their potential gets multiplied by $1.5=3/2$ .

By the choice of $\ell_{i}$ (i.e., maximizing $p(\ell_{i})-p(\overline{\ell}_{i})$ ), we have:

\begin{split}&p(\ell_{i})-p(\overline{\ell}_{i})\geq p(\overline{\ell}_{j})-p(\ell_{j})\\ &\implies a+b+c-d-e-f\geq b+e+h-a-d-g\\ &\implies 2a+0b+1c+0d-2e-1f+1g-1h\geq 0\end{split}

(

\clubsuit

)

Since FindZugzwang() returns NULL, (missing) $\spadesuit$ does not hold in $\psi$ . Thus the following holds:

\begin{split}&\textstyle(a+e)<\frac{5}{4}(b+d)+\frac{1}{2}(c+f+g+h)\\ &\textstyle\implies-1a+\frac{5}{4}b+\frac{1}{2}c+\frac{5}{4}d-1e+\frac{1}{2}f+\frac{1}{2}g+\frac{1}{2}h>0\end{split}

(

\blacklozenge

)

Thus $p(\psi)\geq p(\psi^{\prime})$ because the linear combination $\frac{9}{16}$ (missing) $\clubsuit$ $+\frac{1}{8}$ (missing) $\blacklozenge$ implies:

	$\displaystyle\textstyle\frac{9}{16}\bigl{(}2a+0b+1c+0d-2e-1f+1g-1h\bigr{)}+\frac{1}{8}\bigl{(}-1a+\frac{5}{4}b+\frac{1}{2}c+\frac{5}{4}d-1e+\frac{1}{2}f+\frac{1}{2}g+\frac{1}{2}h\bigr{)}>0$
	$\displaystyle\textstyle\implies 1a+\frac{5}{32}b+\frac{5}{8}c+\frac{5}{32}d-\frac{5}{4}e-\frac{1}{2}f+\frac{5}{8}g-\frac{1}{2}h>0$
	$\displaystyle\textstyle\implies 1a+1b+1c+1d-\frac{5}{4}e-\frac{1}{2}f+1g-\frac{1}{2}h>0$
	$\displaystyle\textstyle\implies a+b+c+d+g-\bigl{(}\frac{5}{4}e+\frac{1}{2}(f+h)\bigr{)}>0$

Acknowledgments

This work was supported by NSF grants CCF-1657377 and CCF-1942742.

References

[AO12] 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.
[Bys04] Jesper Byskov. Maker-Maker and Maker-Breaker games are PSPACE-complete. Technical Report RS-04-14, BRICS, Department of Computer Science, Aarhus University, 2004.
[ES73] Paul Erdős and John Selfridge. On a combinatorial game. Journal of Combinatorial Theory, Series A, 14(3), 1973.
[Kut04] Martin Kutz. The Angel Problem, Positional Games, and Digraph Roots. PhD thesis, Freie Universität Berlin, 2004. Chapter 2: Weak Positional Games.
[Kut05] 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.
[RW20a] Md Lutfar Rahman and Thomas Watson. Complexity of unordered CNF games. ACM Transactions on Computation Theory, 12(3):18:1–18:18, 2020.
[RW20b] 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.
[RW21] 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.
[Sch76] 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.
[Sch78] Thomas Schaefer. On the complexity of some two-person perfect-information games. Journal of Computer and System Sciences, 16(2):185–225, 1978.