Reduction

What is reduction?

Reduction is the single most common technique used in designing algorithms. Reducing one problem $X$ to another problem $Y$ means to write an algorithm for $X$ that uses an algorithm for $Y$ as a black box or subroutine. Crucially, the correctness of the resulting algorithm for $X$ cannot depend in any way on how the algorithm for $Y$ works. The only thing we can assume is that the black box solves $Y$ correctly. The inner workings of the black box are simply none of our business—they’re somebody else’s problem. It’s often best to literally think of the black box as functioning purely by magic.