The final is open notes/book. It is from 2:15-4:15 in Room 205 MLH (our classroom) on Friday, 5/12. Here are the topics you should focus on for the final.

• Space Complexity I: SPACE, NSPACE, Savitch's Theorem, PSPACE, PSPACE-completeness, Proof that TQBF is PSPACE-complete, Examples of other PSPACE-complete problems such as FORMULA-GAME and GENERALIZED GEOGRAPHY. (Chapter 8 and lecture notes)
• Space Complexity II: The classes L and NL, log-space reducibility, NL-completeness, NL-completeness of PATH, Two possible definitions of RL, Proof that if RL is defined without poly(n) time bound then RL = NL, UPATH is in RL, NL = coNL. (Chapter 8 and Lecture notes).
• Time and Space Hierarchy Theorems: Space and time constructible functions, diagonalization proofs of the two hierarchy theorems and their implications. (Chapter 9 and lecture notes)
• Randomized Complexity Classes: Probabilistic TMs, BPP, proof of the amplification lemma for BPP, PRIMES in BPP, RP. (Chapter 10 and lecture notes)
• Approximation Algorithms and Hardness of Approximation: Definition of an approximation algorithm, VERTEX COVER has a 2-approximation, LP-relaxation plus randomized rounding to get a O(log n)-approximation for SET COVER, Hardness of approximation of TSP, Definition of a PCP system, The PCP theorem. (Lecture notes)

  ---