MIT · Computer Science

18.404J Theory of Computation

Michael Sipser · 2020 · 25 free video 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…

▶ Play on Open Lecture HallCourse page ↗

Lectures

  1. Introduction finite automata regular expressions
  2. Nondeterminism closure properties regular expressions 2192 finite automata
  3. Regular pumping lemma finite automata 2192 regular expressions cfgs
  4. Pushdown automata cfg 2194 pda
  5. Cf pumping lemma turing machines
  6. Tm variants church turing thesis
  7. Decision problems for automata and grammars
  8. Lecture 8: undecidability
  9. Lecture 9: reducibility
  10. Lecture 10: computation history method
  11. Lecture 11: recursion theorem and logic
  12. Lecture 12: time complexity
  13. Lecture 14: p and np sat poly time reducibility
  14. Lecture 15: np completeness
  15. Lecture 16: cook levin theorem
  16. Lecture 17: space complexity pspace savitchs theorem
  17. Lecture 18: pspace completeness
  18. Lecture 19: games generalized geography
  19. Lecture 20: l and nl nl conl
  20. Lecture 21: hierarchy theorems
  21. Lecture 22: provably intractable problems oracles
  22. Lecture 23: probabilistic computation bpp
  23. Lecture 24: probabilistic computation cont
  24. Lecture 25: interactive proof systems ip
  25. Lecture 26: conp 2286 ip

From MIT OpenCourseWare · CC BY-NC-SA 4.0. More from MIT.

Open Lecture Hall is free, with no ads and no sign-up. It is not run by or connected to any university; the lectures are the universities' own free recordings, played from where they host them. About & rights