This is a 25-lecture course, with each lecture being about 60-90 minutes, given online by Michael Sipser. It gives an introduction to computability.
This course emphasizes computability and computational complexity theory. Topics include regular and context-free languages, decidable and undecidable problems, reducibility, recursive function theory, time and space measures on computation, completeness, hierarchy theorems, inherently complex problems, oracles, probabilistic computation, and interactive proof systems.
- Introduction, Finite Automata, Regular Expressions
- Non-determinism, Closure Properties, Conversion of Regular Expressions to FA
- Regular Pumping Lemma, Conversion of FA to Regular Expressions
- Pushdown Automata, CFG ⟷ PDA
- CF Pumping Lemma, Turing Machines
- TM Variants, Church-Turing Thesis
- Decision Problems for Automata and Grammars
- Undecidability
- Reducibility
- Computation History Method
- Recursion Theorem and Logic
- Time Complexity
- P and NP, SAT, Poly-Time Reducibility
- NP-Completeness
- Cook-Levin Theorem
- Space Complexity, PSPACE, Savitch’s Theorem
- PSPACE-Completeness
- Games, Generalized Geography
- L and NL, NL = coNL
- Hierarchy Theorems
- Provably Intractable Problems, Oracles
- Probabilistic Computation, BPP
- Probabilistic Computation (cont.)
- Interactive Proof Systems, IP
- coNP is a subset of IP
These videos are of a lecture course by Michael Sipser at the Massachusetts Institute of Technology in 2020, and made available as part of its OpenCourseWare initiative.
