Intuition The one core ideaA problem is NP-hard if it is at least as hard as every problem in the class NP — meaning any NP problem can be quietly rewritten into it. That's it: it's a difficulty floor , not a membership card, so an NP-hard problem might even live above NP (harder than any NP problem, maybe unsolvable).
Before you can read the parent note NP-hard , you need to own every squiggle it uses. This page builds each one from nothing, in the order they depend on each other. Never trust a symbol you haven't seen born.
Definition Decision problemA decision problem is a question whose only allowed answers are YES or NO . Example: "Does this map of cities have a route shorter than 100 km?" — the answer is a single bit.
The picture: a machine with one input slot and exactly two output lamps, a green YES lamp and a red NO lamp.
Intuition Why decision problems and not "give me the number"?The whole theory of NP is built only on YES/NO questions, because YES/NO answers can carry a checkable proof . A question like "what is the shortest route?" outputs a number — there's no single yes/no fact to certify. This is exactly why optimization problems fall outside NP later (see Decision vs Optimization problems ).
Definition The membership symbol∈ x ∈ L x L L YES . So x ∈ L L x
Picture L box . Every input string is either dropped inside the box (a YES-instance) or left outside (a NO-instance).
x ∈ L x x ∈ / L x
The parent note calls these boxes languages . A class is just a box of boxes: a family of problems grouped by how hard they are.
Definition Certificate (a.k.a. witness / proof)A certificate is a short hint that makes a YES-answer obvious to double-check . For "is there a route shorter than 100 km?", the certificate is the route itself — hand it over and anyone can quickly add up the distances.
NP every YES-instance has a certificate that can be checked in polynomial time by a machine called a verifier . (Full detail: Class NP — verifier and certificate definition .)
The picture: two roles.
A prover (untrusted) shouts a certificate.
A verifier (trusted, fast) inspects input + certificate and lights YES only if the hint truly works.
Intuition Why "verify fast" and not "solve fast"?NP does not ask you to find the answer quickly — only to check a given hint quickly. Finding a needle may be brutal; confirming "yes, that's a needle" is instant. NP is the class of "hard to find, easy to check" problems.
Definition Polynomial timeAn algorithm runs in polynomial time if the number of steps it takes is at most n k k n n n 2 n 3 + 5 n Not polynomials: 2 n n !
The picture: two curves rising with input size n
Intuition Why polynomial is the fence for "efficient"?Polynomials stay tame: double the input and n 2 one to the input and 2 n doubles . So we draw the line for "usable in practice" at polynomial. Everything in NP-hardness theory measures cost against this fence.
Common mistake "Polynomial always beats exponential, son 100 Why it feels right: we just said polynomial = efficient.
Fix: n 100 shape of growth (a fixed power vs a moving exponent), not everyday speed. What matters is that a polynomial composed with a polynomial is still a polynomial — the property that makes reductions chain up.
This is the heart of the whole topic, so build it slowly.
Definition A reduction functionf f translator : a polynomial-time function that rewrites an instance x A f ( x ) L x ∈ A ⟺ f ( x ) ∈ L . ⟺ YES on the left exactly when YES on the right " — both directions.
≤ p A ≤ p L A L f A L L A
The picture: a pipe. Pour an A f L that , and the answer is also the answer to A
Intuition Why does the arrow point "toward the harder one"?A ≤ p L A L L A L A ≤ p ≤ right is the heavier one. This direction is the single most-flipped idea in the whole subject (see the parent's mistake list). More detail: Polynomial-time many-one reduction .
Common mistake Confusing which side is the hard one.Fix: In A ≤ p L ≤ left (A right (L prove L left .
Now every symbol in the definition is defined. Read it and nothing is a stranger:
Decision problem YES or NO
Language L a box of YES inputs
Certificate a checkable hint
Polynomial time n to the k
Reduction arrow A leq p L
NP-complete hard and in NP
Transitivity of reductions
The classic seeds that make this machinery run live in Cook–Levin Theorem (the first NP-hard proof), 3-SAT and reduction templates (the reusable starting point), and the boundary cases in Halting Problem — undecidability and P vs NP .
Cover the right side and answer aloud. If any stalls, reread that section before the parent note.
What does x ∈ L The answer to problem L x x
What is a decision problem? A question whose only answers are YES or NO (a single bit).
What is a certificate? A short hint that lets a verifier quickly confirm a YES-answer.
What is the class NP? All decision problems whose YES-instances have a poly-time-checkable certificate.
What is "polynomial time"? Running in at most n k k 2 n
Why is a polynomial-of-a-polynomial still polynomial important? It lets reductions chain: A ≤ p B ≤ p C ⇒ A ≤ p C
What does A ≤ p L A L L
Write the definition of NP-hard using ∈ ≤ p For every A ∈ NP A ≤ p L
NP-hard vs NP-complete? NP-hard = floor beneath NP (may not be in NP); NP-complete = NP-hard AND in NP.
