ConceptTheory & Algos
Satisfiability
The problem of determining if there exists an assignment of truth values to variables that makes a boolean formula true.
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 logic1Formulas1
Opens up
Concepts that name this one as a prerequisite.
Lecturers
1Lectures that assume it
14The first 12 are shown.
- The Complexity Class coNP
- Approximate counting
- Hardness within P
- The Complexity Class NP
- NP-Completeness Reductions
- Cook-Levin Theorem
- Efficient Fine-Grained Algorithms
- Boolean Satisfiability (SAT)
- NP-Completeness and the Cook-Levin Theorem
- Ladner's Theorem and Mahaney's Theorem
- Interactive Proof Systems, IP
- Oracle Turing Machines and P^NP
Connections
21The lectures that define it or assume it, and the concepts next to it.
Concepts6
Lectures15
- Reductions
- The Complexity Class coNP
- Approximate counting
- Hardness within P
- The Complexity Class NP
- NP-Completeness Reductions