JOVANA
Explore Library Glossary Getting Started Three Levels Fields How it works Mission
Join the mission
All guides

Reductions: Comparing Hardness

A reduction is a translator that lets one problem secretly solve another. Learn the exact shape of a polynomial-time reduction, why it points hardness in one specific direction, and how this one idea will soon let a single hard problem condemn thousands at once.

What we are reaching for, and why now

By now this rung has given you two big pieces. You met decision problems and the classes P (decided fast) and NP (a yes-answer can be checked fast given a short certificate, even if finding one seems to need exponential search). You also saw the verifier picture: NP is exactly the problems whose yes-instances carry a tiny proof a polynomial-time checker accepts. Those two guides described single problems in isolation. This guide introduces the tool that lets us compare problems against each other — and comparison, not isolation, is where the whole theory of intractability lives.

Here is the question reduction answers. You have two problems, A and B, and no fast algorithm for either. Are they equally stubborn, or is one secretly harder? It would be wonderful to settle this without solving either — to relate their difficulty directly. A reduction does exactly that: it is a way of turning instances of one problem into instances of another so cleverly that a solver for the second hands you a solver for the first, for free. Once you can transport solvability like this, you can rank problems by hardness — and that ranking is the spine of everything that follows in this rung.

The precise shape of a polynomial-time reduction

Let A and B be decision problems (each instance has a yes/no answer). A polynomial-time reduction from A to B is a single function f, computable in polynomial time, that maps every instance x of A to some instance f(x) of B, with one ironclad promise: x is a yes-instance of A if and only if f(x) is a yes-instance of B. That "if and only if" is the whole game. It means f preserves the answer in both directions — yes maps to yes, no maps to no — so reading off B's answer on f(x) is literally reading off A's answer on x. We write this A <=p B, read "A reduces to B".

  1. Take an arbitrary instance x of A — anything at all, you must handle every case.
  2. Run f to build the instance f(x) of B; this construction must cost only polynomial time in the size of x.
  3. Imagine a (hypothetical) polynomial-time solver for B answers yes or no on f(x).
  4. Return that same answer as the answer for x — correct because f obeys the yes-iff-yes promise.
  5. Conclude: a polynomial-time B-solver, wrapped in f, is a polynomial-time A-solver.

Which way does the arrow point?

This is the single most reversed idea in the whole subject, so let us nail it with care. A reduction A <=p B shows that B is at least as hard as A — not the reverse. The clean way to feel why is to chase the consequences in both directions. *Good news flows from B to A:* if B turns out to be easy (polynomial), then so is A, because we solve A by translating to B and using B's fast solver. *Bad news flows from A to B:* if A is known to be hard, then B must be hard too, because if B were easy, A would inherit that easiness through f — contradicting A's known hardness. So you reduce from the problem you already trust as hard, to the problem you want to indict.

Two structural facts make reductions usable as a ranking. First, reduction is transitive: if A <=p B and B <=p C, then A <=p C, because you can compose the two translators and a composition of polynomial-time functions is still polynomial time. That is what lets hardness chain across long sequences of problems. Second, reductions respect the class boundary: if A <=p B and B is in P, then A is in P. Both facts lean on the same humble engineering point — a polynomial wrapped around a polynomial stays polynomial — which is precisely why we insist the translator f run in polynomial time and not a moment slower.

A worked micro-reduction: 3-SAT into Vertex Cover

Abstract talk only goes so far; let us build a real f. Take 3-SAT (a Boolean satisfiability formula with three literals per clause: is there a true/false assignment making every clause true?) and reduce it to Vertex Cover (given a graph and a number k, is there a set of k vertices touching every edge?). The translation builds a graph in two pieces. For each variable x, add a gadget: two vertices, one labelled x and one labelled not-x, joined by an edge — a tiny tug-of-war forcing the cover to pick exactly one of the pair, which encodes a truth value. For each clause, add a triangle of three vertices, one per literal in that clause.

variable gadget (per variable x):     x ---- not_x      (1 edge)
clause gadget (per clause):       a triangle on its 3 literals
wiring:   join each clause-vertex to its matching variable-vertex
set the budget:   k = (#variables) + 2 * (#clauses)
The construction f: one edge per variable, one triangle per clause, connector edges, and a carefully chosen budget k.

Now finish the wiring and set the budget. Connect each clause-vertex to the variable-vertex carrying the same literal. Then ask for a cover of size k = (number of variables) + 2*(number of clauses). Why exactly that k? Covering a triangle needs at least 2 of its 3 vertices, and covering each variable edge needs at least 1 — so k is the tightest possible budget. Spending it forces a clean choice everywhere: one true literal per variable gadget, and in each triangle the one vertex you can afford to leave out must be covered from the variable side, meaning its literal is true. A size-k cover exists exactly when every clause has a satisfied literal — that is, exactly when the formula is satisfiable. The yes-iff-yes promise holds, and the whole graph is built in time polynomial in the formula's length.

Honest fine print, and where this is heading

A few honest cautions. First, a reduction only relates A and B; on its own it proves nothing absolute. "B is at least as hard as A" is a conditional statement — useful only once you trust something about A. The unconditional power arrives next guide, when Cook-Levin supplies a first problem (SAT) proven hard for all of NP, giving every reduction a solid anchor to push from. Second, the answer-preservation must be exact in both directions: a translator that only guarantees "yes implies yes" but lets some no-instance of A become a yes-instance of B is broken, because B's solver would then say yes where A should say no. Writing the reverse direction is usually where the real work and the real bugs live.

Third, a frequent trap: a reduction does not need to be natural or even insightful, only correct and polynomial-time. Our 3-SAT-to-Vertex-Cover gadgets look like an arbitrary contraption, and that is fine — the formula and the graph have nothing to do with each other intuitively, yet f honestly transports the answer. And do not confuse the two roles a reduction can play. Earlier in this ladder you saw reduction used to carry a lower bound between concrete problems in a comparison model; here it carries membership in a complexity class and the notion of relative hardness. Same logical move — translate cheaply, preserve the answer — just a different currency of "cheap" and "hard".

Step back and see the leverage you now hold. With reduction as a hardness-comparator, a single hard problem stops being one isolated fact: every reduction from it stamps its hardness onto a new target. The next guide makes this dramatic — NP-hardness means "every problem in NP reduces to me", and Cook-Levin proves SAT is such a universal landing spot. From that one seed, a chain of reductions like the one you just built marches hardness across the NP-complete zoo, condemning thousands of problems at a stroke. Reduction is the conveyor belt; the rest of this rung is about what rides on it.