Computability & Complexity
Welcome to the course website for Computability & Complexity! This course asks the two deepest questions in computer science: what can be computed at all, and of the things that can, what can be computed efficiently?
Check out the Course Syllabus for more info!
Announcements
(Announcements for Fall 2026 will appear here.)
Topics Covered
The course is organized into four units:
- Unit 0, Foundations & Review: Proof techniques (induction, contradiction, diagonalization), sets/relations/functions, and asymptotic notation done carefully
- Unit 1, Models of Computation: Finite automata, regular languages, the pumping lemma, context-free grammars, and the Chomsky hierarchy
- Unit 2, Computability: Turing machines, the Church-Turing thesis, decidability, the halting problem, reductions, and Rice's theorem
- Unit 3, Complexity: P, NP, NP-completeness, Cook-Levin, coNP, space complexity, and the hierarchy theorems