We proved that TQBF is PSPACE$-$complete. We can use this to give a second proof

that PSPACE $=$ NPSPACE, by proving that TQBF is also a NPSPACE complete

problem. For this problem, do not assume PSPACE $=$ NPSPACE by Savitch's

theorem, as that is what we are trying to prove, you may only assume PSPACE sube

NPSPACE.

$($a$)(5$ points$)$ Prove that TQBFin NPSPACE $($Hint$,$ you should not be able to show

that TQBFinNP $).$

$($b$)(5$ points$)$ We proved that AALin PSPACE that $L{?}_{p}TQBF.$ Explain how you

could modify the proof we did to show that AALin NPSPACE that $L{?}_{p}TQBF$

$($Hint$,$ why could we show SAT complete for a nondeterministic class, and TQBF

complete for a deterministic one?$)$