NP-hard — harder than NP, may not be in NP: Visual walkthrough

We assume you know nothing. Every word — "reduction", "certificate", "polynomial time" — gets a picture before it gets used.

Step 1 — What is a "problem" here, and what does "answer" mean?

WHAT. In this whole topic a problem means a yes/no question about an input string. The input is written on a strip — call it $x$ . The problem is really the set of all inputs whose answer is "yes". We call that set a language and write it $L$ .

$x \in L$ is shorthand for "the answer to the question, on input $x$ , is yes."
$x \in / L$ means the answer is no.

WHY. Before we can say one problem is "harder" than another, we need a single, uniform shape for every problem. Turning every question into "is this string in this set?" makes them comparable — apples to apples.

PICTURE. Two bins. Every possible input string flies in and lands in the YES bin or the NO bin. The problem is the YES bin.

Step 2 — What is the class NP? (the room of problems with checkable proofs)

WHAT. A problem $A$ is in NP when a yes answer always comes with a short certificate — a proof slip — that a fast checker can verify. Formally there is a verifier $V$ and a polynomial bound so that:

$x \in A ⟺ \exists c (∣ c ∣ \leq ∣ x ∣^{k} and V (x, c) = yes)$

Term by term:

$x$ — the input string (the question).
$c$ — the certificate, the proof slip; the $\exists c$ means "there exists some slip."
$∣ c ∣ \leq ∣ x ∣^{k}$ — the slip is short: its length is at most a polynomial in the input length. ( $k$ is a fixed whole number.)
$V (x, c) = yes$ — the verifier reads $x$ and the slip and, in polynomial time, agrees.

WHY. "Polynomial time" is our meaning of fast: the work grows like $∣ x ∣^{k}$ , not like $2^{∣ x ∣}$ . We demand the slip be short and the check be fast — otherwise "having a proof" would be free and meaningless.

PICTURE. A locked YES answer, a proof slip $c$ handed to a small fast machine $V$ ; if $V$ nods, the input is in the YES bin.

Step 3 — What is a reduction? (pouring one problem into another)

WHAT. A polynomial-time many-one reduction from $A$ to $L$ , written $A \leq_{p} L$ , is a translator function $f$ that:

runs in polynomial time, and
converts every input $x$ of problem $A$ into an input $f (x)$ of problem $L$ preserving the answer:

$x \in A ⟺ f (x) \in L$

Term by term:

$f$ — the translator; you feed it an $A$ -question, it prints an $L$ -question.
"polynomial time" — the translation itself is cheap, so it can never be the source of hardness.
$⟺$ — the two-way arrow guarantees yes stays yes and no stays no. Both directions matter (a one-way arrow would let the translator lie).

WHY. This is the machinery of "at least as hard as." If a fast solver for $L$ existed, you could solve any $A$ -question by: translate with $f$ , then ask the $L$ -solver. Cheap translate + fast solve = fast overall. So $L$ being easy would drag $A$ down to easy too — meaning $L$ is at least as hard as $A$ .

PICTURE. A funnel: $A$ -instances pour in on the left, come out on the right as $L$ -instances, YES-lids staying YES, NO-lids staying NO.

Step 4 — Define NP-hard: make all of NP pour in

WHAT. $L$ is NP-hard when every problem $A$ in NP reduces to it:

$\forall A \in NP : A \leq_{p} L$

Term by term:

$\forall A \in NP$ — "for every problem in the NP room", not just one.
$A \leq_{p} L$ — each of them pours into $L$ by its own translator.

WHY. Step 3 gave " $L$ at least as hard as one problem $A$ ." To capture "at least as hard as the whole class", we simply demand it for all members at once. Notice what is absent: nowhere did we write " $L \in NP$ ." NP-hardness is a lower bound on difficulty and says nothing about a ceiling.

PICTURE. Every problem-bubble in the NP cloud sends its own funnel down into $L$ . $L$ sits below (harder), catching all of them.

Step 5 — The engine: reductions chain (transitivity)

WHAT. If $A \leq_{p} B$ and $B \leq_{p} C$ , then $A \leq_{p} C$ . Two funnels stacked make one funnel.

Let $f$ reduce $A$ to $B$ and $g$ reduce $B$ to $C$ . Build $h (x) = g (f (x))$ :

Fast? $f$ runs in time $p (∣ x ∣)$ , so its output has length $\leq p (∣ x ∣)$ ; then $g$ runs in time $q (p (∣ x ∣))$ . A polynomial of a polynomial is still a polynomial — still fast.
Correct? $x \in A ⟺ f (x) \in B ⟺ g (f (x)) \in C$ , i.e. $x \in A ⟺ h (x) \in C$ .

Symbols:

$h = g \circ f$ — first translate $A \to B$ , then $B \to C$ .
$p, q$ — the two polynomial time bounds; $q \circ p$ is their composition, still polynomial.

WHY. This is why nobody re-reduces all of NP to prove a new problem hard. Prove one link $K \leq_{p} L$ from a known NP-hard $K$ , and transitivity does the rest:

$K already NP-hard A \leq_{p} K and your one new proof K \leq_{p} L ⟹ A \leq_{p} L (\forall A \in NP) .$

PICTURE. Every NP funnel already ends at $K$ ; you attach one more short pipe $K \to L$ , and now everything drains into $L$ .

Step 6 — The seed: Cook–Levin plants the first NP-hard problem

WHAT. Cook–Levin Theorem proves SAT is NP-hard directly: for any $A \in NP$ , its poly-time verifier's whole computation on $(x, c)$ is written as one giant Boolean formula $ϕ_{x}$ . Then

$x \in A ⟺ ϕ_{x} \in SAT .$

$ϕ_{x}$ — a formula whose variables are the tape cells / states at every time-step of the verifier.
A satisfying assignment of $ϕ_{x}$ is an accepting certificate $c$ — so "formula solvable" = "yes-witness exists".
The computation table is $(n^{k}) \times (n^{k})$ cells, each constrained by $O (1)$ clauses → polynomially many clauses → the translation is poly time.

WHY. Without one problem proven NP-hard from scratch, transitivity has nothing to chain from. Cook–Levin is that first domino. SAT is also in NP (guess the assignment, check fast), so SAT lands NP-complete — floor and roof.

PICTURE. The verifier's step-by-step computation grid becomes a wall of clauses; a satisfying assignment lights up exactly one accepting run.

Step 7 — The twist: a problem that is NP-hard but outside NP

WHAT. Take the Halting Problem $HALT = {⟨ M, x ⟩ : M halts on x}$ .

It is NP-hard. Reduce 3-SAT into it: given a formula $ϕ$ , build a machine $M_{ϕ}$ that tries all assignments and halts iff one satisfies $ϕ$ . Building $M_{ϕ}$ is poly time, and $ϕ \in 3-SAT ⟺ ⟨ M_{ϕ}, ϵ ⟩ \in HALT .$ Since 3-SAT is NP-hard, transitivity (Step 5) makes HALT NP-hard.
It is not in NP. HALT is undecidable — no algorithm decides it at all. No decider ⇒ no poly-time verifier ⇒ HALT $\in /$ NP.

Symbols:

$⟨ M, x ⟩$ — an encoding of "machine $M$ run on input $x$ " as one string.
$ϵ$ — the empty input; $M_{ϕ}$ needs no external input, it holds $ϕ$ inside.
"halts iff satisfiable" — the trick that converts "does a yes-witness exist?" into "does this searcher ever stop?".

WHY. This is the whole point of the parent note in one example: NP-hardness only demands the floor (Step 4). HALT sails past the ceiling of NP — it isn't even decidable — yet still catches every NP funnel. That is "harder than NP, may not be in NP."

PICTURE. The NP cloud, the NP-complete rim (floor and roof, e.g. SAT), and far above it the undecidable region where HALT floats — still connected by a funnel to everything below.

The one-picture summary

One map: the NP cloud (problems with short checkable proofs), the NP-complete boundary sitting on the floor and under NP's roof, and the NP-hard region stretching from that floor upward without limit — through the undecidable, where HALT lives. Every arrow is a funnel $A \leq_{p} L$ ; every funnel drains toward greater hardness.

Recall Feynman: the whole walkthrough in plain words

We first agreed every "problem" is just a YES-bin of strings (Step 1). NP is the room of problems where a yes always ships with a short proof slip a fast checker can approve (Step 2). A reduction is a cheap translator that rewrites one problem's questions as another's without flipping any answer — so if the target is easy, the source is easy too (Step 3). Call a problem NP-hard when every problem in the NP room can pour into it through such translators (Step 4) — that says "at least as hard as all of NP", and crucially says nothing about being in NP. To prove new problems hard we don't redo all of NP: funnels chain, so one link from a known-hard problem suffices (Step 5). Cook–Levin plants the first hard problem, SAT, by turning any verifier's computation into a formula (Step 6). And then the twist: the Halting Problem catches every funnel too — it's NP-hard — yet it's undecidable, floating above NP's roof entirely (Step 7). Master key strong enough to open the NP room, even though it lives in a harder room. That's the picture.

Recall Quick self-test

Which direction proves $L$ NP-hard? ::: Reduce a known NP-hard problem into $L$ ( $K \leq_{p} L$ ), never $L \leq_{p} K$ . Why is HALT not in NP? ::: It is undecidable, so no decider and hence no poly-time verifier can exist. What extra condition turns NP-hard into NP-complete? ::: Also being in NP (having a short poly-time-checkable certificate). Why does transitivity let us reuse one reduction? ::: $A \leq_{p} K$ and $K \leq_{p} L$ give $A \leq_{p} L$ , so one new link $K \leq_{p} L$ inherits hardness from all of NP.