2. Nondeterminism, Closure Properties, Conversion of Regular Expressions to FA
3
3. Regular Pumping Lemma, Conversion of FA to Regular Expressions
4
4. Pushdown Automata, Conversion of CFG to PDA and Reverse Conversion
5
5. CF Pumping Lemma, Turing Machines
6
6. TM Variants, Church-Turing Thesis
7
7. Decision Problems for Automata and Grammars
8
8. Undecidability
9
9. Reducibility
10
10. Computation History Method
11
11. Recursion Theorem and Logic
12
12. Time Complexity
13
14. P and NP, SAT, Poly-Time Reducibility
14
15. NP-Completeness
15
16. Cook-Levin Theorem
16
17. Space Complexity, PSPACE, Savitch's Theorem
17
18. PSPACE-Completeness
18
19. Games, Generalized Geography
19
20. L and NL, NL = coNL
20
21. Hierarchy Theorems
21
22. Provably Intractable Problems, Oracles
22
23. Probabilistic Computation, BPP
23
24. Probabilistic Computation (cont.)
24
25. Interactive Proof Systems, IP
25
26. coNP is a subset of IP
Description:
Dive into the world of theoretical computer science with this comprehensive lecture series on the Theory of Computation, taught by Professor Michael Sipser at MIT. Explore fundamental concepts such as finite automata, regular expressions, pushdown automata, Turing machines, and computational complexity theory. Learn about key theorems like Cook-Levin, Savitch's, and Immerman-Szelepcsenyi, while developing a deep understanding of computability and complexity. Progress through 26 lectures covering topics from basic automata to advanced concepts like interactive proof systems, probabilistic computation, and NP-completeness. Gain insights into decision problems, undecidability, reducibility, and space complexity. Engage with this rigorous course to build a strong foundation in theoretical computer science and its applications.