**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*Φ*(*x*_{1}, …,*x*_{n}) be a Boolean CNF formula. Is the following proposional formula true?

∃*x*_{1}∀*x*_{2}∃*x*_{3}∀*x*_{4}…∀*x*_{n − 1}∃*x*_{n}*Φ*(*x*_{1}, …, *x*_{n})

- Amy picks truth value for
*x*_{1}, then Bob for*x*_{2}, then Amy for*x*_{3}, 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*= {*C*_{1}, …,*C*_{n}}**Initial configuration**. Subset*c*_{0}⊆*C*of conditions initially satisfied.**Goal configuration**. Subset $c* \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.

- To invoke operator
**PLANNING**. Is it possible to apply sequence of operators to get from initial configuration to goal configuration?

### 8-Puzzle

九格的板块，缺失一格，每次可以移动到空白处。

**Conditions**.*C*_{ij}, $1 \leq i$,*j*≤ 9, where*C*_{ij}means 数字i在方块9**Initial state**.*c*_{0}= {*C*_{11},*C*_{22}, …,*C*_{66},*C*_{78},*C*_{87},*C*_{99}}**Good state**. $c* = {C_{11}, C_{22}, …, C_{66}, C_{77}, C_{88}, C_{99}}$**Operators**.- Precondition to apply
*O*_{i}= {*C*_{11},*C*_{22}, …,*C*_{66},*C*_{78},*C*_{87},*C*_{99}} - After invoking
*O*_{i}, conditions*C*_{79}and*C*_{98}become true. - After invoking
*O*_{i}, conditions*C*_{78}and*C*_{99}become true.

- Precondition to apply

**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”.

- Include node for each of 2
**PLANNING**Is there a path from*c*_{0}to $c*$ in configuration graph?- Claim. PLANNING in EXPTIME.
- Run BFS to find path from
*c*_{0}to $c*$ in configuration graph.

- Run BFS to find path from
- Configuration graph can have 2
^{n}nodes, and shortest path can be of length = 2^{n}− 1. **Theorem**PLANNING is in PSPACE.**Pf***L*= 2^{n}− 1, where n is number of conditions- Suppose there is a path from
*c*_{1}to*c*_{2}of length ≤ L. - Path from
*c*_{1}to midpoint and from midpoint to*c*_{2}are each ≤ L/2. - Enumerate all possible midpoints.
- Apply recursively. Depth of recursion =
*l**o**g*_{2}*L*.

- Suppose there is a path from

## PSPACE-Complete

Y is PSPACE-complete if:

- Y is in PSPACE
- 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*⊆*N**P*⊆*P**S**P**A**C**E*⊆*E**X**P**T**I**M**E*

## 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 *Φ*(*x*_{1}, …, *x*_{n})=*C*_{1} ∩ *C*_{2} ∩ …*C*_{k} of QSAT.

- Include a node for each literal and its negation and connect them.
- at most one of
*x*_{i}and its negation can be chosen

- at most one of
- Choose a large constant c (e.g., c ≥ k+2), and put weight
*c*^{n − i + 1}on literal*x*_{i}and its negation; set*B*=*c*^{n − 1}+*c*^{n − 3}+ … +*c*^{4}+*c*^{2}+ 1.- This ensures variables are selected in order
*x*_{1},*x*_{2}, …,*x*_{n}.

- This ensures variables are selected in order
- 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
*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, i.e.,
- ∀
*x*_{1}∃*x*_{2}∀*x*_{3}∃*x*_{4}…∃*x*_{n − 1}∀*x*_{n}¬*Φ*(*x*_{1}, …,*x*_{n})⇔∃*x*_{1}∀*x*_{2}∃*x*_{3}∀*x*_{4}…∀*x*_{n − 1}∃*x*_{n}*Φ*(*x*_{1}, …,*x*_{n})

- ∀