Material Covered

1. An introduction to computability theory: What can we compute?

   Turing machines, including the two important variations nondeterminism and alteration.

   Reductions between problems, completeness.

   Recursive, r.e., and not r.e. languages. Rice's Theorem.

2. Complexity theory: How fast can we compute it?
   1. Complexity measures--time and space.
   2. P and NP.
   3. Classes below and above Pand NP: L, NL, the polynomial hierarchy, PSPACE.
   4. Probabilistic complexity classes. (Turing machines that toss coins.)
3. Advanced topics as time allows:
   1. Intro to computational learning theory.
   2. Interactive proofs.
   3. Intro to modern cryptography.