A whole bunch of the proofs in this section are done in the same paper and mainly use this problem. So we’ll go out of order here- but really this is a restatement of the QBF problem from a couple of weeks ago.
The problem: Sequential Truth Assignment. This is problem GP4 in the appendix.
The description: Given a set of variables and a collection of clauses (like a Satisfiability instance), players take turns giving truth assignments to sequential variables. Player 1 wins if and only if all clauses are satisfied. Does player 1 have a forced win?
Example: (x1 ∨ x2 ∨ x3) ∧ (~x1 ∨ ~x2 ∨ ~x3) ∧ (x1 ∨ ~x2 ∨ x3).
Player 1 can win by choosing x1 = true, which satisfies both the first and third clauses. Then layer 2 has to set x2, so should set it to true (otherwise clause 2 is automatically satisfied). but player 1 then set x3 to false satisfying the second clause.
Reduction: The paper by Shaefer that has many of the reductions we’ll be doing in this section refers to the paper by Stockmeyer and Meyer that showed how QBF was NP-Complete (or worse- you might want to check out the comments of the QBF problem for a discussion) defined a formula Bk to be a formula on k sets of variables, with sets alternating between “For All” and “There Exists”. Schaefer points out that if you allow players to assign values to these sets of variables (instead of one at a time, like our problem describes), then player 1 is the “There Exists” player and player 2 is the “For All” player, and you have basically the same problem.
To get to our “one variable at a time” version of the problem, we need to build a problem instance with one variable per set. We can start with an instance of 3SAT and since the variables are set sequentially, we set up the quantifiers to be ∃ x1 ∀ x2 ∃ x3, and so on.
Difficulty: 5. I think it depends on how hard you see the intermediate step of going from QBF to the alternating of setting groups of variables. Knowing you have to break the reduction into 2 steps is a bit hard as well.