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

Polynomial-Time Reductions and NP-Hardness

You already know reductions transfer impossibility between undecidable problems. Now we sharpen the same translator idea to transfer DIFFICULTY: a polynomial-time reduction lets one hard problem hand its hardness to another, and that single tool is how the whole NP-complete family ends up roped together.

Same translator, new cargo: difficulty

You met reductions earlier on this ladder as a way to transfer IMPOSSIBILITY: if I can translate the halting problem into your problem, then your problem must be undecidable too, because a solver for it would solve the halting problem we already proved unsolvable. A reduction is a translator — a recipe that turns every instance of problem A into an instance of problem B, faithfully, so that yes maps to yes and no maps to no. In this rung we keep the very same machine but change the cargo. Instead of transferring 'impossible', we transfer 'apparently very hard'. The translator must now be cheap enough that it cannot be doing the real work in disguise.

Here is the crucial new constraint. A polynomial-time reduction (also called a Karp reduction, or many-one mapping reduction) from A to B is a function f computable in polynomial time in the size of its input, such that x is a yes-instance of A if and only if f(x) is a yes-instance of B. Why must f run in polynomial time? Because if the translator were allowed to take exponential time, it could secretly SOLVE the hard problem on the side and then output a trivial answer — the translation would smuggle the difficulty into the act of translating, and prove nothing. Forcing f to be polynomial keeps it honest: it is only allowed to reshape the question, never to answer it.

Direction is everything (again)

The single most common mistake here is reducing the wrong way, so let us be brutally clear about which way the arrow points. Suppose you want to prove that some new problem NEW is hard. You must reduce a KNOWN-hard problem INTO NEW, i.e. KNOWN <=p NEW. That says: 'if NEW were easy, then KNOWN would be easy too' — and since we believe KNOWN is hard, NEW must be hard as well. If you instead reduce NEW <=p KNOWN, you have only shown NEW is no HARDER than the known-hard problem, which is a true but useless fact: a problem can be easy and still be no harder than a hard one. The hardness flows in one direction only, from the source you trust to be hard into the target you are accusing.

Two more properties make these reductions trustworthy as a hardness currency. First, they COMPOSE: if A <=p B and B <=p C, then A <=p C, because running one polynomial translator after another is still polynomial (a polynomial of a polynomial is a polynomial). Difficulty therefore slides along chains, exactly as undecidability did. Second, polynomial-time reductions respect the class P: if B is in P and A <=p B, then A is in P too — translate, then solve, both cheaply. That second fact is the engine behind everything: the moment ONE NP-hard problem turns out to be solvable in polynomial time, every problem that reduces to it collapses into P along with it.

NP-hard and NP-complete: the two definitions, kept apart

Now we can name the two roles precisely, and they are easy to confuse, so hold them apart. A problem H is NP-hard if EVERY problem in NP reduces to it in polynomial time — H is at least as hard as everything in NP. Notice H itself need not even be in NP; it might be far harder, or not a decision problem at all. A problem is NP-complete if it is BOTH NP-hard AND a member of NP. So NP-complete = the hardest problems that still live inside NP — the simultaneous champions: as hard as anything in NP, yet still equipped with the short, polynomial-time-checkable certificate that membership in NP demands.

This raises a chicken-and-egg worry. To prove a new problem NP-hard we reduce a known NP-hard problem into it — but how did we get the very FIRST one, with nothing yet known to be hard? That is precisely the job of the Cook-Levin theorem, the subject of the next guide: it proves directly, from the bare definition of NP, that Boolean satisfiability (SAT) is NP-complete by showing how any nondeterministic verifier's computation can be encoded as a logical formula. SAT is the seed. Once we have that one anchor, every later NP-completeness proof is a polynomial-time reduction starting (directly or through a chain) from SAT.

Building one for real: 3-SAT reduces to clique

Definitions feel abstract until you watch a reduction get built, so let us construct the classic one: 3-SAT reduces to the clique problem. 3-SAT asks whether a Boolean formula in conjunctive normal form, with exactly three literals per clause, can be made true by some assignment. The clique problem asks whether a graph contains k mutually-connected vertices (a clique of size k). These two questions look like they live in different universes — logic versus graphs — yet a polynomial-time translator turns any 3-SAT formula into a graph whose cliques exactly correspond to satisfying assignments. The bridge is a gadget: a small graph fragment that mimics one piece of the source problem.

  1. Read the formula. Say it has k clauses, each a group of three literals (a variable or its negation), like (x OR y OR not z) AND ... For each literal in each clause, drop one vertex into the graph. A 3-clause formula gives 3k vertices, grouped into k little triples.
  2. Draw an edge between two vertices ONLY IF they sit in DIFFERENT clauses AND they are not contradictory — that is, one is not the negation of the other (never join x to not-x). Deliberately put NO edges inside a clause's own triple.
  3. Now ask the clique question with k = number of clauses. Claim: the formula is satisfiable IF AND ONLY IF this graph has a clique of size k.
  4. See why the 'only if' holds: a satisfying assignment makes at least one literal true in every clause. Pick one such true literal per clause — that is k vertices, one per triple. No two are contradictory (a true literal and its negation cannot both be true), and they are in different clauses, so all the required edges exist. They form a k-clique.
  5. And the 'if' direction: a k-clique must take exactly one vertex from each triple (no edges exist inside a triple, so two vertices from the same clause can never both be in a clique). Set each chosen literal to true; since no two chosen literals contradict, this is a consistent assignment, and it satisfies every clause. Both directions hold, so the reduction is faithful.
Formula:  (x OR y OR z)  AND  (NOT x OR NOT y OR z)     k = 2 clauses

Clause 1 triple:   [x]   [y]   [z]
Clause 2 triple:   [!x]  [!y]  [z]

Edges: connect across clauses, skip contradictory pairs (x--!x, y--!y).
   [z](c1) -- [z](c2)        ok (not contradictory)
   [x](c1) -- [!y](c2)       ok
   [x](c1) -- [!x](c2)       NO  (contradiction)
   ...

A 2-clique = pick one true literal per clause that don't conflict,
e.g. z(c1)--z(c2)  ==>  set z = true  ==>  both clauses satisfied.
The reduction in miniature. The translator only inspects and copies structure — counting clauses, comparing literals — all clearly doable in time polynomial in the formula's length. It never tries to satisfy the formula itself.

Reading what a reduction proves — and what it does not

What did that little construction actually buy us? Since 3-SAT is NP-complete (it inherits SAT's hardness through an earlier reduction), and 3-SAT <=p clique, the clique problem is NP-hard. And clique is itself in NP — given a claimed clique, you just check all its pairs are connected, a fast verification from a short certificate. NP-hard plus in-NP means clique is NP-complete. The same gadget style spreads outward: clique reduces to vertex cover (a clique of size k in a graph corresponds to a vertex cover of size n minus k in the complement graph), 3-SAT reduces to 3-coloring, to Hamiltonian path, to subset-sum and on to the traveling salesman problem. Each link uses a tailor-made gadget, and together they weave the famous web of NP-complete problems you will tour in the final guide.

Be honest about the limits, though. A reduction proves RELATIVE hardness, never absolute. It says 'clique is at least as hard as 3-SAT', which is only as meaningful as our belief that 3-SAT is hard — and that belief rests on the still-OPEN question of whether P equals NP. Nobody has proved any NP-complete problem requires more than polynomial time; it is conjectured, not theorem. Two more cautions worth carrying: a polynomial reduction can still blow the input up by a polynomial factor, so 'polynomial' is not 'free'; and a polynomial-time algorithm with a monstrous exponent like O(n^100) is technically tractable yet useless in practice — remember big-O is an upper bound on worst-case growth, not a promise of real-world speed.

And one misconception to bury for good: a quantum computer is NOT known to crack NP-complete problems efficiently. Quantum machines help with certain structured problems like factoring, but factoring is not believed to be NP-complete, and no efficient quantum algorithm for SAT or clique is known. So when a problem you face turns out to be NP-complete, the realistic response is not to wait for exotic hardware. It is to cope: settle for an approximate answer, lean on heuristics and modern SAT solvers that are fast on real instances despite the worst-case bound, or exploit some small parameter staying small. Reductions are how we recognize this whole family in the first place — and recognizing it is what tells you to stop hunting for a perfect fast algorithm and start coping intelligently.