Formal & Physical Sciences Computing & CybersecurityENUndergrad Complexity at CMU - Lecture 5: Time Hierarchy TheoremRyan O'DonnellJune 24, 2017 80 min★ ★ ★ ★ ★ 5/5Time Hierarchy TheoremComputational ComplexityTuring Machines
Formal & Physical Sciences Computing & CybersecurityENUndergrad Complexity at CMU - Lecture 4: Time Complexity and Universal Turing MachinesRyan O'DonnellJune 24, 2017 77 min★ ★ ★ ★ ★ 5/5Complexity TheoryTime ComplexityTuring Machines
Formal & Physical Sciences Computing & CybersecurityENUndergrad Complexity at CMU - Lecture 14: Ladner's Theorem and Mahaney's TheoremRyan O'DonnellJune 24, 2017 82 min★ ★ ★ ★ ★ 5/5Computational ComplexityLadner's TheoremMahaney's Theorem
Formal & Physical Sciences Computing & CybersecurityENUndergrad Complexity at CMU - Lecture 13: Search-to-Decision, Padding, Dichotomy TheoremsRyan O'DonnellJune 24, 2017 79 min★ ★ ★ ★ ☆ 4/5Computational ComplexitySearch-to-DecisionPadding
Formal & Physical Sciences Computing & CybersecurityENUndergrad Complexity at CMU - Lecture 12: NP-Completeness ReductionsDavid WitmerJune 24, 2017 80 min★ ★ ★ ★ ☆ 4/5NP-CompletenessReductions3SAT
Formal & Physical Sciences Computing & CybersecurityENUndergrad Complexity at CMU - Lecture 3: Simulations and Turing Machine VariantsRyan O'DonnellJune 11, 2017 80 min★ ★ ★ ★ ★ 5/5Turing MachinesComputational ComplexitySimulation
Formal & Physical Sciences Computing & CybersecurityENUndergrad Complexity at CMU - Lecture 2: Turing MachinesRyan O'DonnellJune 11, 2017 79 min★ ★ ★ ★ ★ 5/5Turing MachinesComputational ComplexityTheory of Computation
Formal & Physical Sciences Computing & CybersecurityENUndergrad Complexity at CMU - Lecture 1: Course OverviewRyan O'DonnellJune 7, 2017 79 min★ ★ ★ ★ ☆ 4/5Complexity TheoryP vs NPComputational Complexity
