CMSC 652 -- Complexity Theory

Jonathan Katz

This course is a graduate-level introduction to complexity theory. It is assumed that students have some prior exposure to the basics of computability theory and are familiar with, e.g., Turing machines and the complexity classes P and NP. (Even these topics, however, will be reviewed at the beginning of the semester.)

See below for versions of the course I have taught in the past: