Lecture Notes in Computer Science Vol. 1367, Springer-Verlag, 1998. The actual list of topics may vary slightly from the list that follows below, depending on the interests of the class. The canonical complexity classes, and why they are the fundamental objects of complexity theory. Padding and Translational arguments Alternation , a generalization of nondeterminism, is very useful in relating time and space complexity, and it also models Parallel Computation and Circuit Complexity .
Deterministic circuits simulate probabilistic computation.
2-prover interactive proofs.