198:538: Complexity of Computation
Some notes for the Spring, 2000 version of the class are available here.
- January 20, 2000.
(Preliminaries, Hierarchy Theorems, Recursion Theorem.)
Notes by Taliver Heath.
- January 22, 2000.
(The Speed-Up Theorem -- also known as the Blum Speed-Up Theorem.)
Notes by Jarl Friis.
- January 27, 2000.
(The nondeterministic time hierarchy theorem.)
Notes by Detlef Ronneburger.
- February 5, 2000.
(NL closed under complement, start of proof of NL/poly = UL/poly.)
Notes by Detlef Ronneburger.
- February 10, 2000.
(completion of proof of NL/poly = UL/poly.)
Notes by Taliver Heath.
- April 18-20, 2000.
(Introduction to Interactive Proofs, Graph Isomorphism.)
Notes by Taliver Heath.