Completed
15. NP-Completeness
Class Central Classrooms beta
YouTube videos curated by Class Central.
Classroom Contents
Theory of Computation, Fall 2020
Automatically move to the next video in the Classroom when playback concludes
- 1 1. Introduction, Finite Automata, Regular Expressions
- 2 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
