The next game in the appendix is “Sift”, but the Schaefer paper we’ve been using has that reduction depend on two other problems, so we’ll do those first. Schaefer calls this problem “G_{%free}(CNF)”, I made up the name we’re using.

**The problem: **Pre-Partitioned Truth Assignment. This problem is not in the appendix.

**The description: **Given a CNF formula A, where the variables in A are partitioned into two equal size sets, V_{1} and V_{2. } On player 1’s turn player 1 chooses a variable in V_{1} and chooses to make it true or false, On player 2’s turn, player 2 chooses a variable in V_{2} and chooses to make it true or false. Player 1 wins if the variable assignments made by both players make A true. Does A have a forced win?

**Example:** Here’s the equation from last time: {(x_{1} ∨ x_{2} ∨ x_{3}), (~x_{1} ∨~x_{2}∨ ~x_{3}), (~x_{4}, x_{1}, ~x_{2})} Lets say that V_{1} = {x_{1}, x_{2}} and V_{2} = {x_{3}. x_{4}}. Then player 1 can force a win by setting x_{2} to false on their first turn, making the second and third clauses true. Since player 2 can only set x_{3} or x_{4} on their turn, they can’t stop player 1 from setting x_{1} to true on their next turn, making all clauses true.

Here’s another example where player 1 loses: {(x_{1} ∨ x_{3} ∨ x_{4}), (~x_{1} ∨ x_{3} ∨ x_{4}), (x_{2} ∨ ~x_{3} ∨ ~x_{4}). If we again have V_{1} = {x_{1}, x_{2}} and V_{2} = {x_{3}. x_{4}}, then player 2 wins by setting both x_{3} and x_{4} to false because no matter what player 1 does, they have to set x_{1} somehow, which will make one of the first two clauses false.

**Reduction:** (This problem is Theorem 3.8 in Schaefer’s paper). Just like in most of the reductions in the Schaefer paper, we start with an instance of QBF where we have variables x_{1} through x_{n} (n is assumed to be even), and the formula alternates with “There exists” (starting with x_{1}, on all of the odd-numbered variables up through x_{n-1}) and “For all” (starting with x_{2}, on all of the even-numbered variables up through x_{n}) quantifiers on the variables, leading into a CNF formula A_{0}. We need to build up an instance of Pre-Partitioned Truth Assignment by creating a new formula A’ and the variable sets V_{1} and V_{2}. For each variable in the QBF formula x_{i}, our formula has 3 variables: x_{i}, y_{i}, and z_{i}. V_{1} holds x_{i}, y_{i}, and z_{i+1} when i is odd, and V_{2} holds x_{i}, y_{i}, and z_{i-1} if i is even.

The formula is pretty complicated but is built to force z_{i} to be set by one player to the same value of either x_{i} or y_{i} by the other player (and so must be set *after* the corresponding x_{i} or y_{i} is chosen). The optimal move will be to play z_{i} *immediately* after the corresponding x_{i} or y_{i}, forcing the choice back on the other player. So that player will play the other of x_{i} or y_{i} (rather than open up some other variable’s x or y, only to be responded with by the corresponding z). Then it will be the other player’s turn to choose the next x_{i+1} or y_{i+1}.

The values of x_{i} correspond to the literals in the original QBF formula, so assuming players play “correctly”, player 1 takes the role of the “there exists” player in the QBF formula, and player 2 takes the role of the “for all” player in the formula. And if there is a way to set the x variables in the new formula to make it satisfiable, then there is a way to make the original QBF formula satisfiable.

**Difficulty: **9. For this problem, even Schaefer admits the proof is hard to follow, so he spends a page explaining what the goal of the construction is before diving into the proof. I do like the reappearance of the “triples” of moves where a meaningful decision by a player is followed by 2 forced moves, making the next meaningful decision be placed on the other player.