Advanced Complexity Theory

By the end, you can

• Explain why PSPACE measures memory rather than time and how algorithms can reuse space.
• Name the three main space classes (L, NL, PSPACE), their definitions, and the NL-complete problem.
• State Savitch's theorem and derive the equality PSPACE = NPSPACE from it.
• Describe TQBF as a two-player game and explain why it is PSPACE-complete.
• Build the first few levels of the polynomial hierarchy from alternating quantifiers.
• Explain what it would mean for the hierarchy to collapse, and why P = NP would collapse it entirely.
• Distinguish deciding (NP) from counting (#P) and give an example where counting is harder.
• Contrast the permanent and determinant, and state Toda's theorem.
• Describe the IP model and state the IP = PSPACE result.
• State the PCP theorem and explain its consequence for MAX-3SAT approximation.