Polynomial Reduction
A polynomial reduction converts problem A to problem B in polynomial time; if B is solvable then so is A, and this is used to prove NP-hardness.
Purpose
To prove problem hardness and transfer solvability; a core tool of complexity theory.
Mechanism
A ≤_p B: there is a polynomial-time function f mapping instances of A to instances of B such that A(x)=B(f(x)). If B∈P then A∈P. If A is known NP-hard and A≤_p B, then B is NP-hard.
Use cases
- Complexity proofs
- NP-hard reductions
- Problem classification