Reduction
Defined in 2 lectures. Each definition is in that lecture's terms.
Definitions are written by AI from each lecture’s transcript. The time opens the lecture where the lecturer explains it.
- A partial order on computational problems where problem A is less than or equal to problem B if solving B efficiently implies solving A efficiently.13:08Mathematics and Computation: The Landscape of P vs. NPAvi Wigderson · Institute for Advanced Study
- A reduction from problem A to problem B is a polynomial-time algorithm that converts inputs of problem A into equivalent inputs of problem B.