Learn · Theory of Computation

Lecture 13 of 25Video Lectures1 h 20 min

Lecture 14: P and NP, SAT, Poly-Time Reducibility

Prof. Michael Sipser · Massachusetts Institute of Technology

At MIT OpenCourseWare Transcript

Credits and licence

From
Theory of Computation, Massachusetts Institute of Technology (at MIT OpenCourseWare)
Licence
CC BY-NC-SA 4.0, as MIT OpenCourseWare states it. Non-commercial use only.
Attribution
Prof. Michael Sipser. Theory of Computation. Fall 2020. Massachusetts Institute of Technology: MIT OpenCourseWare, https://ocw.mit.edu/. License: Creative Commons BY-NC-SA.
Who can watch
Tweens profiles and older. How courses are placed

All the lectures

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