MIT 18.404J Theory of Computation, Fall 2020

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