# 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.