We’re going to dive into a couple of logic games for the next couple of posts before we come out with I think of as more “game-like” games.

**The problem: **Variable Partition Truth Assignment. This is problem GP5 in the appendix.

**The description: **Given a set U of variables, and a set C of clauses over U, players play a game where they alternate choosing variables from U. The variables Player 1 chooses will be set true, and the variables Player 2 chooses will be set to false. Player 1 wins if all clauses in C are satisfied. Can player 1 force a win?

**Example: **Here is a small example: The clauses will be: {(x_{1} ∨ x_{2} ∨ x_{3}), (~x_{1} ∨~x_{2}∨ ~x_{3}), (~x_{4}, x_{1}, ~x_{2})}

Player 1 can force a win by choosing x_{1}, which will be set to true. This satisfies both clauses 1 and 3. Player 2 does not want to choose x_{2} or x_{3} (since any variable player 2 chooses will be set to false, making clause 2 true), so they’ll choose x_{4}. Then player 1 picks either of x_{2} or x_{3} (clause 2 is still not satisfied, because the variable must be set to true by player 1), then player 2 must set the other one to false, satisfying clause 2.

**Reduction: **The paper by Schaefer that we’ve been going through calls this “G_{POS} (POS CNF)” and focuses on the subcase where we’re given a formula where all of the variables are positive. If even that case is NP-Complete, then the generalized case where we allow negated literals is also NP-Complete. The reduction in the paper is from Sequential Truth Assignment, specifically the case where the problem has 3 variables per clause. So we’re given an input that is a set of 2n variables, which we can view as alternating between ∃ and ∀, and a set of m clauses with at most 3 literals per clause. We’re going to build a new formula A’ out of many pieces. The variables are all positive, but some of the variable *names* will correspond to negated literals. We’ll have 2n “x” variables, 2n “~x” variables, and 2n “u” variables. He then builds up a pretty crazy formula. The point of the formula is to force a 6-move sequence between the players:

- On move 6k+1 (so the first move of “round” k), player 1 chooses either x
_{2n-2k}or ~x_{2n-2k}to become true. - The next move, player 2 chooses the other of that pair to become false.
- The next move, player 1 chooses u
_{2n-2k}to become true - On moves 6k+4 through 6k+6, we repeat the same sequence, but this time, player 2 can choose whether to make x
_{2n-2k-1}or ~x_{2n-2k-1}false. Then we end with player 2 choosing u_{2n-2k-1}to become false.

Notice how each set of 3 moves corresponds to one truth assignment of one variable in the Sequential Truth Assignment game (which alternates between player 1 and player 2 choosing the assignment). Also, notice how player 1 choosing a variable x_{i} corresponds to setting it true in the Sequential Truth Assignment game, and player 1 choosing a ~x_{i} variable to be set to true corresponds to making the corresponding Sequential Truth Assignment variable false. (The opposite assignments occur when player 2 chooses)

The hard part of the proof (and of the formula) involves all of the various ways the other player can force a win if the sequence above is not followed.

**Difficulty: **9. The formula in the paper is very hard to follow, which is why I didn’t go into it here- I think the important part is how it all works out. Since I couldn’t think of a way to explain it without going on for pages, I figured just explaining the idea was a better strategy.