ConceptTheory & Algos
SAT
The counting problem of determining the exact number of satisfying assignments for a given Boolean formula.
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.
Boolean formula2Boolean logic1Boolean satisfiability (SAT)1Computational complexity1coNP1NP-complete1NP-hardness1Satisfiability problem1
Opens up
Concepts that name this one as a prerequisite.
Lecturers
2Each in their own terms, from the easiest level.
Michael Sipser
Ryan O'Donnell
A famous and well-studied problem of determining if a boolean formula is satisfiable.
Lectures that assume it
19The first 12 are shown.
- The Complexity Class coNP
- Approximate counting
- Symbolic Execution
- NP-Completeness Reductions
- Time/Space Tradeoffs for SAT
- The Polynomial Hierarchy
- Ironic Complexity
- Toda's 1st Theorem and the Permanent
- Instance Checking and the Permanent
- Cook-Levin Theorem
- Boolean Satisfiability (SAT)
- Ladner's Theorem and Mahaney's Theorem
Connections
30The lectures that define it or assume it, and the concepts next to it.
Concepts7
- Computational complexity
- coNP
- Search-to-decision reduction
- Succinct SAT
- Valiant-Vazirani theorem
- $\Sigma_i-\mathrm{SAT}$
Show 1 moreShow fewer
Lectures23
- P and NP, SAT, Poly-Time Reducibility
- Space Complexity, PSPACE, Savitch's Theorem
- coNP is a Subset of IP
- Quantum Algorithms Synthesis II: Grover's Search & Circuit SAT
- The Complexity Class coNP
- Approximate counting
Show 17 moreShow fewer
- Symbolic Execution
- NP-Completeness Reductions
- Time/Space Tradeoffs for SAT
- The Polynomial Hierarchy
- Ironic Complexity
- Toda's 1st Theorem and the Permanent
- Instance Checking and the Permanent
- Cook-Levin Theorem
- Boolean Satisfiability (SAT)
- Ladner's Theorem and Mahaney's Theorem
- From P-Completeness to PSPACE-Completeness
- Interactive Proof Systems, IP
- Oracle Turing Machines and P^NP
- L and NL, NL = coNL
- Oracles, and the Polynomial Time Hierarchy vs. circuits
- Introduction to Arthur-Merlin classes, MA and AM
- Quasilinear Cook–Levin Theorem