Lecture 18: PSPACE-Completeness

Om kurset

Description: Quickly reviewed last lecture. Proved Savitch’s Theorem: NSPACE\((f(n))\) ⊆ SPACE\((f^2 (n))\). Also proved PSPACE-completeness and \(TQBF\) is PSPACE-complete. Instructor: Prof. Michael Sipser