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
- Introduction finite automata regular expressions
- Nondeterminism closure properties regular expressions 2192 finite automata
- Regular pumping lemma finite automata 2192 regular expressions cfgs
- Pushdown automata cfg 2194 pda
- Cf pumping lemma turing machines
- Tm variants church turing thesis
- 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 savitchs 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 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