CS 483: Theory of Computation

Topics include:

1. Turing machines and the Church-Turing thesis

2. Decidability, the halting problem

3. Reducibility, undecidable problems

4. Decidability of logical theories, Kolmogorov complexity

5. Time classes: P, NP, and NP-complete

6. Space classes: Savitch's theorem, PSPACE-completeness, and NL-completeness

7. Hierarchy theorems, approximation algorithms, probabilistic algorithms

8. Parallel computation, cryptography

2004.08