a reduction

Imagine you only own a calculator that does multiplication, and someone hands you a squaring task: compute n squared. You do not need a new gadget. You just translate the new task into the old one: feed n and n into the multiplier and read off the answer. A reduction is exactly this kind of translation. It turns a problem you want to solve into a problem you already know how to solve, in such a way that an answer to the second hands you the answer to the first.

More precisely, a reduction from problem A to problem B is a recipe that, given any instance (input) of A, produces an instance of B, with the guarantee that the B-answer tells you the A-answer. If you also have a method that solves B, you can now solve A: take your A-instance, translate it to a B-instance, solve B, and translate the answer back. We say A reduces to B, often written A <= B, read as 'A is no harder than B'. The arrow of dependence goes one way: solving B lets you solve A, so B is at least as hard as A. In theory-of-computation we insist the translation itself be computable (a Turing machine can carry it out), so the reduction does not smuggle in any uncomputable power.

Reductions are the workhorse of this whole subject, used in two opposite-feeling directions. To show a problem is solvable, you reduce it to something you can already solve. To show a problem is hard or impossible, you reduce a known-hard problem to it: if A is undecidable and A <= B, then B must be undecidable too, because a solver for B would give a solver for A. Getting that direction backwards is the single most common mistake students make, so guard it carefully (see the direction of a reduction). The same idea reappears later, counting resources instead of mere solvability, as the polynomial-time reductions that define NP-completeness.