PSPACE

\mathcal{P}. Decision problems solvable in polynomial time.

PSPACE. Decision problems solvable in polynomial space.

PSPACE: facts

Binary counter. Count from 0 to 2^n - 1 in binary.
Algorithm. Use n-bit “odometer”.

• exponential time, polynomial space
• space can be reused

Various classes of problems

Quantified satisfiability

QSAT. Let \Phi(x_1, .., x_n) be a boolean CNF formula. Is the following propositional formula true?

\exists x_1 \forall x_2 \exists x_3 \forall x_4 \ldots \exists x_{n-1} \forall x_n \Phi(x_1, .., x_n),\ \text{assume $n$ is odd}

Intuition. Amy picks truth value for x_1, then Bob for x_2, then Amy for x_3, and so on. Can Amy satisfy \Phi no matter what Bob does?

Q-SAT \in PSPACE

Theorem. Q-SAT \in PSPACE.
Pf. Recursively try all possibilities.

• Only need one bit of information from each subproblem.
• Amount of space is proportional to depth of function call stack.

15-puzzle

8-puzzle, 15-puzzle. [Noyes Chapman 1874]

• Board: 3-by-3 grid of tiles labeled 1 .. 8.
• Legal move: slide neighboring tile into blank (white) square.
• Find sequence of legal moves to transform initial configuration into goal configuration.

Planning problem

Conditions. Set C = \{ C_1, .., C_n \}.
Initial configuration. Subset c_0 \subseteq C of conditions initially satisfied.
Goal configuration. Subset c^\ast \subseteq C of conditions we seek to satisfy.
Operators. Set O = \{ O_1, .., O_k \}.

• To invoke operator O_i, must satisfy certain prereq conditions.
• After invoking O_i certain conditions become true, and certain conditions become false.

Planning problem: 8-puzzle

Planning example. Can we solve the 8-puzzle?

Solution. No solution to 8-puzzle or 15-puzzle!

Diversion: Why is 8-puzzle unsolvable?

8-puzzle invariant. Any legal move preserves the parity of the number of pairs of pieces in reverse order (inversions).

Planning problem: binary counter

Planning example. Can we increment an n-bit counter from the all-zeroes state to the all-ones state?

Conditions. C_1, .., C_n: C_i corresponds to bit-i = 1.
Initial state. c_0 = \emptyset: all 0s.
Goal state. c^\ast = \{ C_1, .., C_n \}: all 1s.
Operators. O_1, .., O_n.

• To invoke operator O_i, must satisfy C_1, .., C_{i–1}: i-1 least significant bits are 1.
• After invoking O_i, condition C_i becomes true: set bit i to 1.
• After invoking O_i, conditions C_1, .., C_{i–1} become false: set i-1 least significant bits to 0.

Solution. \{ \} \Rightarrow \{C_1\} \Rightarrow \{C_2\} \Rightarrow \{C_1, C_2\} \Rightarrow \{C_3\} \Rightarrow \{C_3, C_1\} \Rightarrow ..

Observation. Any solution requires at least 2^n - 1 steps.

PLANNING \in EXPTIME

Configuration graph G.

• Include node for each of 2^n possible configurations.
• Include an edge from configuration c' to configuration c'' if one of the operators can convert from c' to c''.

PLANNING. Is there a path from c_0 to c^\ast in configuration graph?

PLANNING \in PSPACE

Theorem. PLANNING \in PSPACE.
Pf.

• Suppose there is a path from c_1 to c_2 of length L.
• Path from c_1 to midpoint and from c_2 to midpoint are each \le L / 2.
• Enumerate all possible midpoints.
• Apply recursively. Depth of recursion = \log_2 L.

hasPath(c_1, c_2, L)

1. if (L ≤ 1) return correct answer;
2. foreach configuration c'
   1. x = hasPath(c_1, c', L/2);
   2. y = hasPath(c_2, c', L/2);
   3. if (x and y) return true;
3. return false;

PSPACE-complete

PSPACE. Decision problems solvable in polynomial space.

PSPACE-complete. Problem Y \in PSPACE-complete if (i) Y \in PSPACE and (ii) for every problem X \in PSPACE, X \le_P Y.

• “hardest” PSPACE-complete problem

PSPACE-complete problems

More PSPACE-complete problems.

• Competitive facility location.
• Natural generalizations of games.
• Given a memory restricted Turing machine, does it terminate in at most k steps?
• Do two regular expressions describe different languages?
• Is it possible to move and rotate complicated object with attachments through an irregularly shaped corridor?
• Is a deadlock state possible within a system of communicating processors?

Competitive facility location

Input. Graph G = (V, E) with positive edge weights, and target B.
Game. Two competing players alternate in selecting nodes. Not allowed to select a node if any of its neighbors has been selected.

Competitive facility location. Can second player guarantee at least B units of profit?

• yes if B = 20; no if B = 25

COMPETITIVE-LOC \in PSPACE-complete

Claim. COMPETITIVE-FACILITY-LOCATION \in PSPACE-complete.
Pf.

• To solve in poly-space, use recursion like Q-SAT, but at each step there are up to n choices instead of 2.
• To show that it’s complete, we show that Q-SAT polynomial reduces to it:
  • Given an instance of Q-SAT, we construct an instance of COMPETITIVE- FACILITY-LOCATION so that player 2 can force a win iff Q-SAT formula is true.

COMPETITIVE-LOC \in PSPACE-complete

Construction. Given instance \Phi(x_1, .., x_n) = C_1 \wedge C_1 \wedge .. \wedge C_k of Q-SAT.

• Include a node for each literal and its negation and connect them. (at most one of x_i and its negation can be chosen)
• Choose c \ge k + 2, and put weight c^i on literal x_i and its negation; set B = c^{n–1} + c^{n–3} + .. + c^4 + c^2 + 1. (ensures variables are selected in order x_n, x_{n–1}, .., x_1)
• As is, player 2 will lose by 1 unit: c^{n–1} + c^{n–3} + .. + c^4 + c^2.

COMPETITIVE-LOC \in PSPACE-complete

Construction. Given instance \Phi(x_1, .., x_n) = C_1 \wedge C_1 \wedge .. \wedge C_k of Q-SAT.

• Give player 2 one last move on which she can try to win.
• For each clause C_j, add node with value 1 and an edge to each of its literals.
• Player 2 can make last move iff truth assignment defined alternately by the players failed to satisfy some clause.