ConceptTheory & Algos
Polynomial time reduction
A method to transform one problem into another using an algorithm that runs in polynomial time.
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.
Opens up
Concepts that name this one as a prerequisite.
Lecturers
2Each in their own terms, from the easiest level.
Ryan O'Donnell
Michael Sipser
A reduction from problem A to problem B that can be computed in polynomial time, such that if B is in P then A is in P.
Lectures that assume it
29The first 12 are shown.
- The Complexity Class coNP
- Complexity: Fixed-Parameter Algorithms
- Exponential Time Hypotheses: ETH and SETH
- Hardness within P
- PSPACE-Completeness
- NP-Completeness Reductions
- Permanent is #P-complete
- The Polynomial Hierarchy
- Ironic Complexity
- Search-to-Decision, Padding, Dichotomy Theorems
- Instance Checking and the Permanent
- Cook-Levin Theorem
Connections
45The lectures that define it or assume it, and the concepts next to it.
Concepts10
Show 4 moreShow fewer
Lectures35
- Games, Generalized Geography
- The Immerman-Szelepcsényi Theorem
- Reductions
- NP-Completeness
- Time Hierarchy Theorem
- Linear Programming: Optimization Reduces to Feasibility
Show 29 moreShow fewer
- The Complexity Class coNP
- Complexity: Fixed-Parameter Algorithms
- Exponential Time Hypotheses: ETH and SETH
- Hardness within P
- PSPACE-Completeness
- NP-Completeness Reductions
- Permanent is #P-complete
- The Polynomial Hierarchy
- Ironic Complexity
- Search-to-Decision, Padding, Dichotomy Theorems
- Instance Checking and the Permanent
- Cook-Levin Theorem
- NP-Completeness and the Cook-Levin Theorem
- Ladner's Theorem and Mahaney's Theorem
- From P-Completeness to PSPACE-Completeness
- Interactive Proof Systems, IP
- Dinur's Proof of the PCP Theorem: Outline
- Oracle Turing Machines and P^NP
- Toda's Second Theorem and Lower Bounds for Uniform ACC
- Space Complexity, PSPACE, Savitch's Theorem
- L and NL, NL = coNL
- Provably Intractable Problems, Oracles
- Oracles, and the Polynomial Time Hierarchy vs. circuits
- Statement of the PCP Theorem
- Beyond Worst-Case Analysis
- The Polynomial Time Hierarchy
- Probabilistically Checkable Proofs of Proximity
- Quasilinear Cook–Levin Theorem
- Quantum Algorithms Synthesis III: Efficient Factoring & BQP