Catalog

Theory of Computation

Mathematics MIT CC BY-NC-SA 4.0 25 lectures

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.

Syllabus

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

Course materials