An introduction to computability theory and computational complexity, focusing on the limits of computation. Subjects include undecidability, NP-completeness, time and space complexity, circuit complexity, and randomized complexity. Three lecture hours a week for one semester.