NP-Complete Explained (Cook-Levin Theorem)
What makes a problem "harder" than another problem? How can we say a problem is the hardest in a complexity class? In this video, we provide a proof sketch of the Cook-Levin theorem, introducing a critical concept known as NP-completeness.
Created by: Cory Chang
Produced by: Vivian Liu
Script Editor: Justin Chen, Zachary Greenberg, Elaine Chang, Brandon Chen
Music: Gravity Sound (https://www.youtube.com/channel/UCQ7Xmyu6eXpJfkEoMtRMv1w)
Twitter: https://twitter.com/UBehavior
—
References:
P vs NP Playlist: https://www.youtube.com/playlist?list=PLlwsleWT767dnN25K_QgvdKkovK_t4K6-
Cook-Levin Theorem: https://en.wikipedia.org/wiki/Cook–Levin_theorem
NP-Completeness: https://en.wikipedia.org/wiki/NP-completeness
Reduction: https://en.wikipedia.org/wiki/Reduction_(complexity)
SAT: https://en.wikipedia.org/wiki/Boolean_satisfiability_problem
Circuit-SAT: https://en.wikipedia.org/wiki/Circuit_satisfiability_problem
Circuits: https://en.wikipedia.org/wiki/Boolean_circuit
Turing Machine: https://en.wikipedia.org/wiki/Turing_machine
Lectures:
NP-Completeness and the Cook--Levin Theorem: https://youtu.be/QRYYDvgGQd0
Видео NP-Complete Explained (Cook-Levin Theorem) канала Undefined Behavior
Created by: Cory Chang
Produced by: Vivian Liu
Script Editor: Justin Chen, Zachary Greenberg, Elaine Chang, Brandon Chen
Music: Gravity Sound (https://www.youtube.com/channel/UCQ7Xmyu6eXpJfkEoMtRMv1w)
Twitter: https://twitter.com/UBehavior
—
References:
P vs NP Playlist: https://www.youtube.com/playlist?list=PLlwsleWT767dnN25K_QgvdKkovK_t4K6-
Cook-Levin Theorem: https://en.wikipedia.org/wiki/Cook–Levin_theorem
NP-Completeness: https://en.wikipedia.org/wiki/NP-completeness
Reduction: https://en.wikipedia.org/wiki/Reduction_(complexity)
SAT: https://en.wikipedia.org/wiki/Boolean_satisfiability_problem
Circuit-SAT: https://en.wikipedia.org/wiki/Circuit_satisfiability_problem
Circuits: https://en.wikipedia.org/wiki/Boolean_circuit
Turing Machine: https://en.wikipedia.org/wiki/Turing_machine
Lectures:
NP-Completeness and the Cook--Levin Theorem: https://youtu.be/QRYYDvgGQd0
Видео NP-Complete Explained (Cook-Levin Theorem) канала Undefined Behavior
Показать
Комментарии отсутствуют
Информация о видео
Другие видео канала
P vs. NP - An IntroductionImpossible Programs (The Halting Problem)16. Complexity: P, NP, NP-completeness, ReductionsNP-Complete Reductions: Clique, Independent Set, Vertex Cover, and Dominating SetWhat Is Big O? (Comparing Algorithms)P vs NP on TV - ComputerphileThe SAT problem8.1 NP-Hard Graph Problem - Clique Decision ProblemIs Democracy Impossible? (Arrow's Theorem)Reduction : 3-CNF SAT to Subset SumWhat Makes P vs. NP So Hard? (P ≠ EXPTIME, Time Hierarchy, Baker-Gill-Solovay)8. NP-Hard and NP-Complete ProblemsCook Levin Theorem - Intro to Theoretical Computer ScienceDoes P=NP? | Richard Karp and Lex FridmanGraph Data Structure 4. Dijkstra’s Shortest Path AlgorithmR8. NP-Complete ProblemsP vs. NP and the Computational Complexity ZooWhat Makes Mario NP-Hard? (Polynomial Reductions)A working definition of NP-hard (Stephen Boyd, Stanford)Why is P vs NP Important?