# PSPACE Completeness

PDF of Prof. Santosh’s handwritten notes is here.

Recall $PSPACE = \bigcup_k SPACE(n^k)$

Analogously to NP-completeness, we can define a notion of being PSPACE-complete. $L$ is PSPACE-complete if

1. $L \in PSPACE$
2. L is PSPACE-Hard i.e. for all $L' \in PSPACE$, $L' \hookrightarrow_P L$

Note that in point 2 above, the reduction should be polynomial time so that if $L \in P$ and PSPACE-complete, then PSPACE=P.

Definition: Totally Quantified Boolean Formula (TQBF) is the language of SAT instances where every literal has a quantifier (either $\exists$ or $\forall$) and the formula has a satisfying assignment.

Example: $\exists x_1 \forall x_2 \exists x_3 (x_1 \wedge \bar{x_2} \wedge x_3)$

Theorem: TQBF is PSPACE-Complete

Proof:

$\mathbf{TQBF \in PSPACE}$

$CHECK(F(x_1, x_2, \dots, x_n))$

• If all variables are set, return value of $F$ on this assignment
• If $\exists x_1$: return $CHECK(F(x_1=0, x_2, \dots, x_n)) \vee CHECK(F(x_1=1, x_2, \dots, x_n))$
• Else $\forall x_1$: return $CHECK(F(x_1=0, x_2, \dots, x_n)) \wedge CHECK(F(x_1=1, x_2, \dots, x_n))$

The above formula decides TQBF in polynomial space as the depth of the recursion is at most $n$ and each level of recursion uses space proportional to the size of the formula $F$.

TQBF is PSPACE-Hard i.e. $\forall L \in PSPACE$, there exists a polynomial time reduction from $L$ to TQBF

Let $L \in PSPACE$. Thus, $\exists$ TM M that decides $L$ using polynomial space.

Consider the configurations of $M$. Let $C_{start}$ be the starting configuration and let $C_{accept}$ be an accepting configuration.

If $M$ uses $O(n^k)$ space, the graph consisting of configurations of $M$ will have $O(exp(n^k))$ vertices. Thus, the path from $C_{start}$ to $C_{accept}$ may involve an exponential number of nodes. Let’s attempt to use the $PATH$ algorithm from the proof of Savitch’s theorem.

$PATH(u,v,t):$

• If $t=0$, check if $u = v$
• If $t=1$, check if there is an edge from $u$ to $v$
• Check $\exists w:$ $PATH(u,w,\frac{t}{2}) \wedge PATH(w,v,\frac{t}{2})$

The above algorithm has at most $O(\log{(exp(n^k)}) = O(n^k)$ levels of recursion, however, the size of the formula doubles at each level. So instead, let’s try to use the $\forall$ quantifier as well.

$\exists w$ $\forall (x,y) \in \{(u,w), (w,v)\}$ $PATH(x,y,\frac{t}{2})$

We need to write $(x,y) \in \{(u,w), (w,v)\}$ as a Boolean formula.

$(x,y) = (u,w) \vee (x,y) = (w,v) \Rightarrow F$

Observe the following:

• $(x,y) = (u,v) \Leftrightarrow (x = u) \wedge (y = v) \Leftrightarrow ((x \wedge u) \vee (\bar{x} \wedge \bar{u})) \wedge ((y \wedge v) \vee (\bar{y} \wedge \bar{v}))$
• $(A \Rightarrow B) \Leftrightarrow (\bar{A} \vee B)$

Using the relations above, we can transform the formula into a quantified boolean formula and apply this recursively.

Thus, there are $O(n^k)$ levels of recursion and the size of the formula increases by $O(n^k)$ at each level. Thus, the size of the final formula and the time used to derive it is $O(n^{2k})$.

Hence, given any language $L \in PSPACE$, we can obtain an equivalent TQBF that has size polynomial in the size of the input, and the construction takes polynomial time.

Thus, TQBF is PSPACE-Complete.