Solving by translation
A reduction converts one problem into another so that a solution to the second yields a solution to the first. Reductions are a foundational tool, used both to solve problems by borrowing existing algorithms and to prove that problems are hard.
How a reduction works
To reduce problem A to problem B you build a transformation.
- Take any instance of A and convert it into an instance of B.
- Solve B with an existing algorithm.
- Translate the answer for B back into an answer for A.
If the transformation runs efficiently, then a fast solver for B gives a fast solver for A.
Two uses
- Algorithmic reuse: if you can phrase your problem as an instance of one you already know how to solve, such as casting a scheduling task as shortest path, you reuse that machinery.
- Hardness proofs: to show a new problem is at least as hard as a known hard one, reduce the known hard problem to the new one. This is exactly how NP completeness spreads.
Direction matters
The direction of the reduction is easy to get backwards. Reducing a hard problem to your problem proves your problem is hard, while reducing your problem to an easy one helps you solve it.
Key idea
A reduction transforms instances of one problem into another and maps answers back, letting you reuse known algorithms or prove hardness, with the direction of the reduction determining which conclusion you can draw.