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 (   / @gravitysound  )

Twitter:   / ubehavior  

—

References:
P vs NP Playlist:    • P vs NP  
Cook-Levin Theorem: https://en.wikipedia.org/wiki/Cook–Le...
NP-Completeness: https://en.wikipedia.org/wiki/NP-comp...
Reduction: https://en.wikipedia.org/wiki/Reducti...)
SAT: https://en.wikipedia.org/wiki/Boolean...
Circuit-SAT: https://en.wikipedia.org/wiki/Circuit...
Circuits: https://en.wikipedia.org/wiki/Boolean...
Turing Machine: https://en.wikipedia.org/wiki/Turing_...

Lectures:
NP-Completeness and the Cook--Levin Theorem:    • Undergrad Complexity at CMU - Lecture...