Completed
Undergrad Complexity at CMU - Lecture 3: Simulations and Turing Machine Variants
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?
