Analogously to NP-completeness, we can define a notion of being PSPACE-complete. is PSPACE-complete if
- L is PSPACE-Hard i.e. for all ,
Note that in point 2 above, the reduction should be polynomial time so that if 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 or ) and the formula has a satisfying assignment.
Theorem: TQBF is PSPACE-Complete
- If all variables are set, return value of on this assignment
- If : return
- Else : return
The above formula decides TQBF in polynomial space as the depth of the recursion is at most and each level of recursion uses space proportional to the size of the formula .
TQBF is PSPACE-Hard i.e. , there exists a polynomial time reduction from to TQBF
Let . Thus, TM M that decides using polynomial space.
Consider the configurations of . Let be the starting configuration and let be an accepting configuration.
If uses space, the graph consisting of configurations of will have vertices. Thus, the path from to may involve an exponential number of nodes. Let’s attempt to use the algorithm from the proof of Savitch’s theorem.
- If , check if
- If , check if there is an edge from to
The above algorithm has at most levels of recursion, however, the size of the formula doubles at each level. So instead, let’s try to use the quantifier as well.
We need to write as a Boolean formula.
Observe the following:
Using the relations above, we can transform the formula into a quantified boolean formula and apply this recursively.
Thus, there are levels of recursion and the size of the formula increases by at each level. Thus, the size of the final formula and the time used to derive it is .
Hence, given any language , 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.