# 算法设计与分析笔记0x0F —— PSPACE

P Decision problems solvable in polynomial time.
PSPACE Decision problems solvable in polynomial space.

• P PSPACE
• 3-SAT is in PSPACE
• NP PSPACE

## Quantifies Satisfiability

• QSAT Let Φ(x1, …, xn) be a Boolean CNF formula. Is the following proposional formula true?

x1x2x3x4…∀xn − 1xnΦ(x1, …, xn)

• Amy picks truth value for x1, then Bob for x2, then Amy for x3, and so on. Can Amy satisfy Φ no matter what Bob does?
• Theorem QSAT 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.

## Planning Problem

• Conditions. Set C = {C1, …, Cn}
• Initial configuration. Subset c0 ⊆ C of conditions initially satisfied.
• Goal configuration. Subset $c* \subseteq C$ of conditions we seek to satisfy.
• Operators. Set O = {O1, …, Ok}
• To invoke operator Oi, must satisfy certain prereq conditions.
• After invoking Oi certain conditions become true, and certain conditions become false.
• PLANNING. Is it possible to apply sequence of operators to get from initial configuration to goal configuration?

### 8-Puzzle

• Conditions. Cij, $1 \leq i$, j ≤ 9, where Cij means 数字i在方块9
• Initial state. c0 = {C11, C22, …, C66, C78, C87, C99}
• Good state. $c* = {C_{11}, C_{22}, …, C_{66}, C_{77}, C_{88}, C_{99}}$
• Operators.
• Precondition to apply Oi = {C11, C22, …, C66, C78, C87, C99}
• After invoking Oi, conditions C79 and C98 become true.
• After invoking Oi, conditions C78 and C99 become true.
• Configuration graph G
• Include node for each of 2n 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 c0 to $c*$ in configuration graph?
• Claim. PLANNING in EXPTIME.
• Run BFS to find path from c0 to $c*$ in configuration graph.
• Configuration graph can have 2n nodes, and shortest path can be of length = 2n − 1.
• Theorem PLANNING is in PSPACE.
• Pf L = 2n − 1, where n is number of conditions
• Suppose there is a path from c1 to c2 of length L.
• Path from c1 to midpoint and from midpoint to c2 are each L/2.
• Enumerate all possible midpoints.
• Apply recursively. Depth of recursion = log2L.

## PSPACE-Complete

Y is PSPACE-complete if:

1. Y is in PSPACE
2. For every problem X in PSPACE, X p Y

• QSAT is PSPACE-complete.
• PSPACE EXPTIME
• Previous algorithm solves QSAT in exponential time, and QSAT is PSPACE-complete.
• Summary P ⊆ NP ⊆ PSPACE ⊆ EXPTIME

## Competitive Facility Location

• Input. Graph with positive node weights, and target number 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?
• Claim. COMPETITIVE-FACILITY is PSPACE-complete.
• Pf.
• To solve it in poly-space, use recursion like QSAT, but at each step there are up to n choices instead of 2.

To show that it’s complete, we show that QSAT polynomial reduces to it. Given an instance of QSAT , we construct an instance of COMPETITIVE-FACILITY such that player 2 can force a win iff QSAT formula is false.
Construction Given instance Φ(x1, …, xn)=C1 ∩ C2 ∩ …Ck of QSAT.

• Include a node for each literal and its negation and connect them.
• at most one of xi and its negation can be chosen
• Choose a large constant c (e.g., c k+2), and put weight cn − i + 1 on literal xi and its negation; set B = cn − 1 + cn − 3 + … + c4 + c2 + 1.
• This ensures variables are selected in order x1, x2, …, xn.
• As is, player 2 will lose by 1 unit: $c^{n-1} + c^{n-3} + … + c^4 + c^2$.
• Give player 2 one last move on which she can try to win.
• For each clause Cj, 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, i.e.,
• x1x2x3x4…∃xn − 1xn¬Φ(x1, …, xn)⇔∃x1x2x3x4…∀xn − 1xnΦ(x1, …, xn)