Completed
Undergrad Complexity at CMU - Lecture 2: Turing Machines
Class Central Classrooms beta
YouTube videos curated by Class Central.
Classroom Contents
Undergraduate Computational Complexity Theory
Automatically move to the next video in the Classroom when playback concludes
- 1 Undergrad Complexity at CMU - Lecture 1: Course Overview
- 2 Undergrad Complexity at CMU - Lecture 2: Turing Machines
- 3 Undergrad Complexity at CMU - Lecture 3: Simulations and Turing Machine Variants
- 4 Undergrad Complexity at CMU - Lecture 4: Time Complexity and Universal Turing Machines
- 5 Undergrad Complexity at CMU - Lecture 5: Time Hierarchy Theorem
- 6 Undergrad Complexity at CMU - Lecture 6: Problems in P
- 7 Undergrad Complexity at CMU - Lecture 7: SAT
- 8 Undergrad Complexity at CMU - Lecture 8: NP
- 9 Undergrad Complexity at CMU - Lecture 9: Nondeterminism
- 10 Undergrad Complexity at CMU - Lecture 10: Reductions
- 11 Undergrad Complexity at CMU - Lecture 11: NP-Completeness and the Cook--Levin Theorem
- 12 Undergrad Complexity at CMU - Lecture 12: NP-Completeness Reductions
- 13 Undergrad Complexity at CMU - Lecture 13: Search-to-Decision, Padding, Dichotomy Theorems
- 14 Undergrad Complexity at CMU - Lecture 14: Ladner's Theorem and Mahaney's Theorem
- 15 Undergrad Complexity at CMU - Lecture 15: coNP
- 16 Undergrad Complexity at CMU - Lecture 16: Space Complexity
- 17 Undergrad Complexity at CMU - Lecture 17: Savitch's Theorem and NL
- 18 Undergrad Complexity at CMU - Lecture 18: NL-Completeness and Logspace Reductions
- 19 Undergrad Complexity at CMU - Lecture 19: From P-Completeness to PSPACE-Completeness
- 20 Undergrad Complexity at CMU - Lecture 20: The Immerman--Szelepcsényi Theorem
- 21 Undergrad Complexity at CMU - Lecture 21: Randomized Complexity: RP, coRP, and ZPP
- 22 Undergrad Complexity at CMU - Lecture 22: BPP
- 23 Undergrad Complexity at CMU - Lecture 23: The Polynomial Hierarchy
- 24 Undergrad Complexity at CMU - Lecture 24: Oracle Turing Machines and P^NP
- 25 Undergrad Complexity at CMU - Lecture 25: Interactive Proofs: IP=PSPACE
- 26 Undergrad Complexity at CMU - Lecture 26: Beyond Worst-Case Analysis
- 27 Undergrad Complexity at CMU - Lecture 27: Hardness within P
- 28 Undergrad Complexity at CMU - Lecture 28: Why is P vs. NP Difficult?
