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: Proof techniques (induction, contradiction, diagonalization), sets, functions, and countability
- Unit 1, Models of Computation: Finite automata, regular expressions, the pumping lemma, context-free grammars, and pushdown automata
- Unit 2, Computability: Turing machines, the Church-Turing thesis, decidability, the halting problem, reductions, and Rice's theorem
- Unit 3, Complexity: Asymptotic notation, P, NP, polynomial-time verifiers, and NP-completeness