ConceptTheory & Algos
Cook-Levin theorem
A theorem stating that every language in NP reduces in polynomial time to CIRCUIT-SAT.
Know first
Named as a prerequisite by the lectures that define this. The number is how many say so. A grey one has no page yet.
NP-completeness5Turing machine4NP3Polynomial time reduction3Boolean circuit2Polynomial time2Boolean satisfiability (SAT)1Boolean satisfiability problem1
Opens up
Concepts that name this one as a prerequisite.
Lecturers
3Each in their own terms, from the easiest level.
Ryan O'Donnell
Michael Sipser
The theorem stating that the Boolean satisfiability problem (SAT) is NP-complete.Yu Zhao
A theorem stating that every language in NP can be reduced to SAT in polynomial time.
Lectures that assume it
1Connections
17The lectures that define it or assume it, and the concepts next to it.
Concepts8
- NP-completeness
- Turing machine
- NP
- Polynomial time reduction
- Boolean circuit
- Recursive formula construction