ConceptTheory & Algos
Decision problem
Any problem with a yes or no answer.
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.
Computability2String2Algorithm1Computation1Computers1Encodings of mathematical objects1Function1Graph1
Opens up
Concepts that name this one as a prerequisite.
Lecturers
3Each in their own terms, from the easiest level.
Ryan O'Donnell
An algorithmic problem where the input is given and the output is a single yes-no bit.Erik Demaine
Problems where the answer is a single bit, either yes or no.
Lectures that assume it
15The first 12 are shown.
- Course Overview, Interval Scheduling
- Complexity: Fixed-Parameter Algorithms
- Approximate counting
- Pseudorandom Generators
- Expander Graph Application 2: Derandomization
- Complexity and Computability with Closed Timelike Curves
- The Complexity Class NP
- NP-Completeness Reductions
- Search-to-Decision, Padding, Dichotomy Theorems
- Boolean Satisfiability (SAT)
- NP-Completeness and the Cook-Levin Theorem
- Savitch's Theorem and NL
Connections
32The lectures that define it or assume it, and the concepts next to it.
Concepts9
Show 3 moreShow fewer
Lectures23
- Complexity: P, NP, NP-completeness, Reductions
- Course Overview and Formal Definition of Computation
- How Hard is too Hard? An Introduction to Complexity
- Turing Machines
- Course Introduction and Overview
- Computational Complexity
Show 17 moreShow fewer
- Quantum Query Complexity
- Quantum Complexity
- Course Overview, Interval Scheduling
- Complexity: Fixed-Parameter Algorithms
- Approximate counting
- Pseudorandom Generators
- Expander Graph Application 2: Derandomization
- Complexity and Computability with Closed Timelike Curves
- The Complexity Class NP
- NP-Completeness Reductions
- Search-to-Decision, Padding, Dichotomy Theorems
- Boolean Satisfiability (SAT)
- NP-Completeness and the Cook-Levin Theorem
- Savitch's Theorem and NL
- Problems in P
- Oracles, and the Polynomial Time Hierarchy vs. circuits
- Beyond Worst-Case Analysis