22C:131 Limits of Computation: Study Guide for Final
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)