MIT 18.404J Theory of Computation | Fall 2020

课程大纲（25 讲）

1. P1 · 1. Introduction, Finite Automata, Regular Expressions60 分钟
2. P2 · 2. Nondeterminism, Closure Properties, Conversion of Regular Expressions to FA63 分钟
3. P3 · 3. Regular Pumping Lemma, Conversion of FA to Regular Expressions70 分钟
4. P4 · 4. Pushdown Automata, Conversion of CFG to PDA and Reverse Conversion69 分钟
5. P5 · 5. CF Pumping Lemma, Turing Machines73 分钟
6. P6 · 6. TM Variants, Church-Turing Thesis74 分钟
7. P7 · 7. Decision Problems for Automata and Grammars76 分钟
8. P8 · 8. Undecidability77 分钟
9. P9 · 9. Reducibility76 分钟
10. P10 · 10. Computation History Method81 分钟
11. P11 · 11. Recursion Theorem and Logic77 分钟
12. P12 · 12. Time Complexity85 分钟
13. P13 · 14. P and NP, SAT, Poly-Time Reducibility79 分钟
14. P14 · 15. NP-Completeness85 分钟
15. P15 · 16. Cook-Levin Theorem78 分钟
16. P16 · 17. Space Complexity, PSPACE, Savitch's Theorem80 分钟
17. P17 · 18. PSPACE-Completeness77 分钟
18. P18 · 19. Games, Generalized Geography79 分钟
19. P19 · 20. L and NL, NL = coNL80 分钟
20. P20 · 21. Hierarchy Theorems81 分钟
21. P21 · 22. Provably Intractable Problems, Oracles82 分钟
22. P22 · 23. Probabilistic Computation, BPP83 分钟
23. P23 · 24. Probabilistic Computation (cont.)83 分钟
24. P24 · 25. Interactive Proof Systems, IP74 分钟
25. P25 · 26. coNP is a subset of IP83 分钟