Tag Archives: QBF

Pre-Partitioned Truth Assignment

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, V1 and V2.   On player 1’s turn player 1 chooses a variable in V1 and chooses to make it true or false,  On player 2’s turn, player 2 chooses a variable in V2 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: {(x1 ∨ x2 ∨ x3), (~x1 ∨~x2∨ ~x3), (~x4, x1, ~x2)}  Lets say that V1 = {x1, x2} and V2 = {x3. x4}.  Then player 1 can force a win by setting x2 to false on their first turn, making the second and third clauses true.  Since player 2 can only set x3 or x4 on their turn, they can’t stop player 1 from setting x1 to true on their next turn, making all clauses true.

Here’s another example where player 1 loses: {(x1  ∨ x3 ∨ x4), (~x1 ∨ x3 ∨ x4), (x2 ∨ ~x3 ∨ ~x4).  If we again have  V1 = {x1, x2} and V2 = {x3. x4}, then player 2 wins by setting both x3 and x4 to false because no matter what player 1 does, they have to set x1 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 x1 through xn (n is assumed to be even), and the formula alternates with “There exists” (starting with x1, on all of the odd-numbered variables up through xn-1) and “For all” (starting with x2, on all of the even-numbered variables up through xn) quantifiers on the variables, leading into a CNF formula A0.  We need to build up an instance of Pre-Partitioned Truth Assignment by creating a new formula A’ and the variable sets V1 and V2.  For each variable in the QBF formula xi, our formula has 3 variables: xi, yi, and zi.  V1 holds xi, yi, and zi+1 when i is odd, and V2 holds xi, yi, and zi-1 if  i is even.

The formula is pretty complicated but is built to force zi to be set by one player to the same value of either xi or yi by the other player (and so must be set after the corresponding xi or yi is chosen).  The optimal move will be to play zi immediately after the corresponding xi or yi, forcing the choice back on the other player.  So that player will play the other of xi or yi (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 xi+1 or yi+1.

The values of xi 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.

Generalized Kayles

I hadn’t heard of this game before encountering this problem.  It sort of feels a lot like Nim to me.

The problem: Generalized Kayles.  This is problem GP3 in the appendix.

The description: Given a graph G=(V,E). Players take turns removing vertices and all vertices adjacent to it from the graph.  The first player to have no vertices left loses.

Example: Here’s a graph:

Suppose player 1 chooses vertex c.  Then we also remove s,b, d, and t.  All that is left are vertices a and e.  Whichever vertex player 2 chooses, player 1 can choose the other one, and win.

Reduction: This one is again by Schaefer, and again uses the same problem which is either Sequential Truth Assignment or QBF, depending on how you look at it.

Just like last time, we’re given a formula: (∃ x1) (∀ x2) (∃ x3) … (∃ xn) (A1 ∧ A2 ∧ … Am), where each Ai is a disjunction of literals.  We’ll further assume n is odd (so the last quantifier is ∃).  The graph is built as follows:

  • Each clause k in the formula gets a vertex x0,k.  These vertices are all connected to each other.
  • Each variable xi in the formula gets two vertices: xi and ~xi, that have an edge between them. We also get y vertices: yi,j for all j 0 <= j < i
  • We add an edge between xi and x0,k if xi appears as a literal in clause k.  Similarly, we add an edge between ~xi and x0,k if ~xi appears as a literal in clause k.
  • Each yi,j vertex connects to all xk vertices where k <= i.  Each yi,j vertex also connects to all ya,b vertices where a < i and b < a.

Here’s a picture from the paper of what we get:

One main point that comes out of this construction is that players need to take their first n moves playing the x (or ~x) vertices in order.  If you go out of order, the opponent can play a y vertex and remove everything.  If you play a y vertex, the opponent can play an x vertex (or an x0 vertex) and remove everything.

If the original formula was satisfiable, player 1 (who is the ∃ player) starts by choosing either x1 or ~x1.  No matter which of x2 or ~x2 is chosen by the opponent (the ∀ player), player3 will have a way to set x3 to keep the formula satisfiable.  This process continues for all variables.  Once player 1 plays the last variable (xn or ~xn), all vertices have been removed from the graph- most importantly, all of the x0 vertices have been removed, because there is an edge from each one to each variable whose setting would satisfy the clause.  Thus, player 2 has no place to play, and player 1 wins.

If the formula is not satisfiable, then after taking turns choosing xi or ~xi for all i, there is still some x0 vertex in the graph (corresponding to a clause not satisfied by the variable choices made).  Player 2 can select that vertex, removing all x0 vertices from the graph, and will win.

Difficulty: 7.  I can see what the “jobs” of each vertex are: The xi  set the truth values of a variable, the x0 ensure that each clause is satisfied by a variable setting, and the y vertices are there to force players to choose the xi vertices in order.  I don’t think I could have come up with this though.

 

Generalized Geography

It’s spring break here- I was expecting to take the week off, but got this post done anyway.  This might mean I skip next week though.

The problem: Generalized Geography.  This is problem GP2 in the appendix.

The description: Given a directed graph G=(V,A) and a starting vertex vo.  Players alternate choosing edges that leave the current vertex (starting with v0.  The next current vertex is the one at the end of the edge leaving from vo.  You can’t choose an edge that is already chosen.  The first player to be unable to choose an edge loses.  Does Player 1 have a forced win?

Example: This is the “geography” game kids play in the car, where you have to think of a place that has as its first letter the last letter of the previous choice.  As a graph problem, vertices correspond to letters, and edges to locations:

Note that the vertices can have self-loops, and (at least in the actual game) could have multiple edges between pairs of vertices.  There is no requirement to have any edges leave a vertex either- I remember instituting the “Phoenix rule”  on car trips because nobody could think of a place that started with X.

Anyway, if we start at E, player 1 has a forced win- they have to take “Egypt” to T, and then player 2 has to take “Texas” to S, and if player 1 chooses “Singapore” we’re in vertex E, it’s player 2’s turn, and they have no place left to pick.  (The actual game has many more edges, of course)

Reduction:  Schaefer says he’s building off of the Sequential Truth Assignment problem from last time, but his instance looks more like an instance of QBF. (I think this is a result of his claim that they’re basically the same problem).  So we’re given a formula: (∃ x1) (∀ x2) (∃ x3) … (∃ xn) (A1 ∧ A2 ∧ … Am), where each Ai is a disjunction of literals.  We’ll further assume n is odd (so the last quantifier is ∃)

We then go on to build a graph.  Each positive and negative literal gets a vertex.  Each variable x1 gets 4 vertices in the graph:

  • xi corresponding to a positive literal
  • ~xi corresponding to a negative literal
  • 2 vertices u and v that control the “entrance” and “exit” for the setting of one of the 2 literal values.

We have a vertex for each clause (yi), and an additional vertex un+1 so the last vi has someplace to go.

Each set of these 4 vertices are set up in a diamond, with edges from ui to both xi and ~xi, and then from both of those to vi. vi then connects to ui+1, making a chain of diamonds. The final un+1 connects to each y vertex, and each y vertex connects to the literals that are in its clause.

Here’s the example picture from the paper:

Player 1 starts on vertex u1. The player chooses whether to make variable x1 positive or negative by going to that vertex (simulating a “there exists”), and player 2 has no choice but to move on to the v1 vertex, and player 1 has no choice to move to the next u2 (simulating a “for all”). This alternating process continues until we hit vertex un+1.  Since there are an odd number of variables, it is now player 2’s turn.

If the setting of the variables has not satisfied some clause, player 2 can move to the y vertex of that unsatisfied clause.  Then player 1 has to go to one of the 3 literals that appear in that clause.  Since the clause was not satisfied, all of these variables have not been chosen, so the edge from that literal to the v vertex is available for player 2 to pick.  But after that, the vertex from the v vertex to the next u vertex has already been chosen, so player 1 loses.

If the setting of the variables has satisfied every clause, then player 2 has to pick a move to a y vertex that has a literal chosen by a player to satisfy it. When player 1 moves to that vertex, the only edge exiting that vertex has already been chosen, so player 2 loses.

Difficulty: 7. I think this is very slick and elegant, but I don’t see a student getting there without lots of help.

Sequential Truth Assignment

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.

Protected: Generalized Hex

This content is password protected. To view it please enter your password below:

Protected: Quantified Boolean Formulas

This content is password protected. To view it please enter your password below: