1:00:34

1. Introduction, Finite Automata, Regular Expressions

MIT OpenCourseWare

1:03:27

2. Nondeterminism, Closure Properties, Conversion of Regular Expressions to FA

MIT OpenCourseWare

1:10:02

3. Regular Pumping Lemma, Conversion of FA to Regular Expressions

MIT OpenCourseWare

1:09:23

4. Pushdown Automata, Conversion of CFG to PDA and Reverse Conversion

MIT OpenCourseWare

1:13:59

5. CF Pumping Lemma, Turing Machines

MIT OpenCourseWare

1:14:49

6. TM Variants, Church-Turing Thesis

MIT OpenCourseWare

1:16:51

7. Decision Problems for Automata and Grammars

MIT OpenCourseWare

1:17:02

8. Undecidability

MIT OpenCourseWare

1:16:37

9. Reducibility

MIT OpenCourseWare

1:21:41

10. Computation History Method

MIT OpenCourseWare

1:17:32

11. Recursion Theorem and Logic

MIT OpenCourseWare

1:25:37

12. Time Complexity

MIT OpenCourseWare

1:19:23

14. P and NP, SAT, Poly-Time Reducibility

MIT OpenCourseWare

1:25:53

15. NP-Completeness

MIT OpenCourseWare

1:18:27

16. Cook-Levin Theorem

MIT OpenCourseWare

1:20:10

17. Space Complexity, PSPACE, Savitch's Theorem

MIT OpenCourseWare

1:17:36

18. PSPACE-Completeness

MIT OpenCourseWare

1:19:38

19. Games, Generalized Geography

MIT OpenCourseWare

1:20:06

20. L and NL, NL = coNL

MIT OpenCourseWare

1:21:57

21. Hierarchy Theorems

MIT OpenCourseWare

1:22:50

22. Provably Intractable Problems, Oracles

MIT OpenCourseWare

1:23:41

23. Probabilistic Computation, BPP

MIT OpenCourseWare

1:23:16

24. Probabilistic Computation (cont.)

MIT OpenCourseWare

1:14:30

25. Interactive Proof Systems, IP

MIT OpenCourseWare

1:23:30

26. coNP is a subset of IP

MIT OpenCourseWare