Text Book - Algorithm Design by Jon Kleinberg and Eva Tardos

Chapter 9 - PSPACE: A Class of Problems beyond NP

Exercises

Q1. Let's consider a special case of Quantified 3-SAT in which the underlying Boolean formula has no negated variables. Specifically, let Φ(x₁,..., x_n) be a Boolean formula of the form

C₁ ∧ C₂ ∧ ... ∧ C_k,

where each C_i is a disjunction of three terms. We say Φ is monotone if each term in each clause consists of a non-negated variable-that is, each term is equal to x_i, for some i, rather than x_i^-.

We define Monotone QSAT to be the decision problem

∃x₁∀x₂ ⋅ ⋅ ⋅∃x_n-2∀x_n-1∃x_nΦ(x₁,...,x_n)?

where the formula Φ is monotone.

Do one of the following two things: (a) prove that Monotone QSAT is PSPACE-complete; or (b) give an algorithm to solve arbitrary instances of Monotone QSAT that runs in time polynomial in n. (Note that in (b), the goal is polynomial time, not just polynomial space.)

Q2. Consider the following word game, which we'll call Geography. You have a set of names of places, like the capital cities of all the countries in the world. The first player begins the game by naming the capital city c of the country the players are in; the second player must then choose a city c' that starts with the letter on which c ends; and the game continues in this way, with each player alternately choosing a city that starts with the letter on which the previous one ended. The player who loses is the first one who cannot choose a city that hasn't been named earlier in the game.

For example, a game played in Hungary would start with "Budapest," and then it could continue (for example), "Tokyo, Ottawa, Ankara, Amsterdam, Moscow, Washington, Nairobi." This game is a good test of geographical knowledge, of course, but even with a list of the world's capitals sitting in front of you, it's also a major strategic challenge. Which word should you pick next, to try forcing your opponent into a situation where they'll be the one who's ultimately stuck without a move?

To highlight the strategic aspect, we define the following abstract version of the game, which we call Geography on a Graph. Here, we have a directed graph G = (V, E), and a designated start node s ∈ V. Players alternate turns starting from s; each player must, if possible, follow an edge out of the current node to a node that hasn't been visited before. The player who loses is the first one who cannot move to a node that hasn't been visited earlier in the game. (There is a direct analogy to Geography, with nodes corresponding to words.) In other words, a player loses if the game is currently at node v, and for edges of the form (v, w), the node w has already been visited.

Prove that it is PSPACE-complete to decide whether the first player can force a win in Geography on a Graph.

Q3. Give a polynomial-time algorithm to decide whether a player has a forced win in Geography on a Graph, in the special case when the underlying graph G has no directed cycles (in other words, when G is a DAG).