CMPT 308
Lecture 18 (PSPACE completeness)

Read: pp. 287-288, 294-302.

Def. A language L is PSPACE-complete if
(i) L is in PSPACE, and
(ii) every language A in PSPACE is polytime reducible to L.


TQBF = { <phi> | phi is a true quantified Boolean formula }

Thm: TQBF is PSPACE-complete.

Proof Idea: (1) TQBF is in PSPACE, by a simple recursive algorithm for
testing the truth a qbf. 

(2) To reduce a PSPACE language to TQBF, we define a qbf

phi_{c1,c2,t}

such that phi_{c1,c2,t} is True iff a given pspace-bounded TM M
on a given input w gets from configuration c1 to configuration c2
in at most t steps.

The base case of t=1 is easy to handle.

For general t>1, we use recursion, with a clever trick to re-use
formulas. (This is similar to Savitch's trick to re-use space.)
See Sipser's book for details.