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.
Overview
Syllabus
- Lecture 1: Introduction, Finite Automata, Regular Expressions
- Lecture 2: Nondeterminism, Closure Properties, Regular Expressions → Finite Automata
- Lecture 3: Regular Pumping Lemma, Finite Automata → Regular Expressions, CFGs
- Lecture 4: Pushdown Automata, CFG ↔ PDA
- Lecture 5: CF Pumping Lemma, Turing Machines
- Lecture 6: TM Variants, Church-Turing Thesis
- Lecture 7: Decision Problems for Automata and Grammars
- Lecture 8: Undecidability
- Lecture 9: Reducibility
- Lecture 10: Computation History Method
- Lecture 11: Recursion Theorem and Logic
- Lecture 12: Time Complexity
- Lecture 14: P and NP, SAT, Poly-Time Reducibility
- Lecture 15: NP-Completeness
- Lecture 16: Cook-Levin Theorem
- Lecture 17: Space Complexity, PSPACE, Savitch's Theorem
- Lecture 18: PSPACE-Completeness
- Lecture 19: Games, Generalized Geography
- Lecture 20: L and NL, NL = coNL
- Lecture 21: Hierarchy Theorems
- Lecture 22: Provably Intractable Problems, Oracles
- Lecture 23: Probabilistic Computation, BPP
- Lecture 24: Probabilistic Computation (cont.)
- Lecture 25: Interactive Proof Systems, IP
- Lecture 26: coNP ⊆ IP
Taught by
Prof. Michael Sipser
