NP-hard — harder than NP, may not be in NP: Worked examples

The scenario matrix

Every NP-hardness situation sits in one of these cells. The examples below are labelled with the cell they cover.

#	Case class	What distinguishes it	Is it in NP?	Example
A	Seed — hardness from scratch	proven hard directly via Cook–Levin Theorem, not by inheriting	Yes (NP-complete)	Ex 1: SAT
B	Inherited hardness (decision, in NP)	one reduction from a known-hard problem	Yes (NP-complete)	Ex 2: Clique
C	Undecidable (above NP, no algorithm)	hard and no decider exists	No	Ex 3: HALT
D	Optimization (wrong type for NP)	outputs a number, not yes/no	No	Ex 4: TSP-opt
E	Counting (#P-style, wrong type)	outputs a count, not yes/no	No	Ex 5: #SAT
F	Degenerate / trivial input	empty or fixed instance — does hardness survive?	edge	Ex 6: SAT on 0 clauses
G	Real-world word problem	translate a story into the framework	—	Ex 7: exam scheduling
H	Exam twist: wrong reduction direction	catch the classic mistake	—	Ex 8: direction trap

We now fill every cell.

Example 1 — Cell A: the seed (SAT is NP-hard directly)

Worked example SAT, proven hard without borrowing from anyone

Statement. SAT $= {ϕ : ϕ$ is a Boolean formula that has some TRUE/FALSE assignment making it true $}$ . Show SAT is NP-hard from first principles (no earlier hard problem to lean on).

Forecast: Guess — where does the "hardness of all of NP at once" come from if we have no earlier hard problem to reduce from? (Hint: it must come from the definition of NP itself.)

Take an arbitrary $A \in$ NP. By definition $A$ has a verifier $V$ (a machine) that, given input $x$ and a short certificate $c$ , decides " $x \in A$ ?" in $\leq n^{k}$ steps. Why this step? We cannot borrow hardness, so we must reach every NP problem — the only handle we have is the verifier every NP problem is guaranteed to own.
Write the verifier's run as a formula $ϕ_{x}$ . Make Boolean variables for each tape cell, head position, and state at each time step $t = 0, 1, \dots, n^{k}$ . Add clauses forcing "row $t + 1$ follows legally from row $t$ " and "the last row is accepting." Why this step? A satisfying assignment then is a valid accepting run — so a good certificate $c$ exists iff $ϕ_{x}$ is satisfiable.
Conclude $x \in A ⟺ ϕ_{x} \in$ SAT, and building $ϕ_{x}$ takes poly time (the tableau is $n^{k} \times n^{k}$ cells, $O (1)$ clauses each). This is the Cook–Levin Theorem.

Verify: Count clauses. Tableau size $= (n^{k})^{2} = n^{2 k}$ cells, each cell needs a constant $C$ clauses, so total $= C n^{2 k}$ — a polynomial in $n$ . For $n = 10, k = 2, C = 8$ that is $8 \cdot 1 0^{4} = 80000$ clauses: large but polynomial, not exponential. ✓ Because every $A \in$ NP reduces to SAT, SAT is NP-hard; a satisfying assignment is a poly-checkable certificate, so SAT $\in$ NP too → NP-complete.

Example 2 — Cell B: inherited hardness, still in NP

Worked example CLIQUE is NP-hard by one reduction

Statement. $CLIQUE = {⟨ G, k ⟩ : G$ has $k$ mutually-connected vertices $}$ . Show it is NP-hard using $3-SAT \leq_{p} CLIQUE$ .

Forecast: Do we re-reduce all of NP again? Guess how many reductions we actually need. (Answer: exactly one, thanks to transitivity.)

Pick the known-hard problem $K =$ 3-SAT (NP-hard from Ex 1 + Cook–Levin Theorem). Why this step? Transitivity lets $K$ carry all of NP: if $A \leq_{p} K$ for all $A \in$ NP and $K \leq_{p} L$ , then $A \leq_{p} L$ . One reduction suffices.
Build the graph from a 3-SAT formula $ϕ$ with $m$ clauses. Put one vertex per literal in each clause ( $3 m$ vertices). Connect two vertices iff they are in different clauses and not negations of each other. Why this step? A $k = m$ -clique must pick one literal per clause, all mutually consistent — exactly a satisfying assignment.
Answer preserved: $ϕ$ satisfiable $⟺$ graph has an $m$ -clique. Construction is poly time (build $3 m$ vertices, $O (m^{2})$ edges).

Verify (concrete tiny case). Take $ϕ = (x) \land (\neg x)$ : $m = 2$ clauses, vertices ${x_{1}}$ (clause 1) and ${\neg x_{2}}$ (clause 2). Edge rule: different clauses ✓ but $x$ and $\neg x$ are negations → no edge. So no 2-clique exists → CLIQUE says NO. And indeed $(x) \land (\neg x)$ is unsatisfiable. Answers match. ✓ CLIQUE has a certificate (the $k$ vertices, checkable in poly time) → in NP → NP-complete.

Example 3 — Cell C: undecidable, NP-hard, NOT in NP

Worked example HALT is NP-hard yet sits above NP

Statement. $HALT = {⟨ M, x ⟩ : M$ halts on input $x}$ . Show HALT is NP-hard but $\in /$ NP.

Forecast: Can something with no algorithm at all still be "at least as hard as NP"? Guess yes/no before reading. (Yes — hardness is a lower bound; there is no ceiling.)

Reduce 3-SAT $\leq_{p}$ HALT. Given $ϕ$ , build a machine $M_{ϕ}$ that loops through all $2^{v}$ assignments and halts iff it finds one satisfying $ϕ$ (otherwise loops forever). Why this step? It converts "does a yes-witness exist?" into "does this searcher ever stop?" — the native question of HALT.
Check the reduction is poly time. We only write down the code of $M_{ϕ}$ ; we do not run it. Writing $M_{ϕ}$ takes size $O (∣ ϕ ∣)$ . Why this step? A reduction is measured by the translation cost, never the target's solving cost.
Answer preserved: $ϕ \in$ 3-SAT $⟺ ⟨ M_{ϕ}, ϵ ⟩ \in$ HALT. Since 3-SAT is NP-hard, transitivity makes HALT NP-hard.
Not in NP. HALT is undecidable (Halting Problem — undecidability) — no algorithm decides it, so certainly no poly-time verifier. Hence HALT $\in /$ NP.

Verify. Consistency check: if HALT were in NP it would be decidable (NP $\subseteq$ decidable). But HALT is undecidable, contradiction. So the "NP-hard but not in NP" claim is not just allowed — it is forced. ✓

Example 4 — Cell D: optimization, wrong type for NP

Worked example TSP-optimization is NP-hard, not in NP

Statement. TSP-opt: output the minimum tour length through $n$ cities. Contrast with TSP-decision: "is there a tour of length $\leq k$ ?" See Decision vs Optimization problems.

Forecast: TSP-decision is NP-complete. Is TSP-opt "even harder", "same", or "a different type"? Guess. (It's a different type — that is why it fails NP membership.)

NP-hard? Given TSP-opt's answer (the number $OPT$ ), answer TSP-decision by comparing $OPT \leq k$ . So TSP-decision $\leq_{p}$ TSP-opt, and TSP-decision is NP-hard → TSP-opt is NP-hard. Why this step? One call to the optimizer settles the (NP-hard) decision question.
In NP? NP is a class of yes/no languages with poly-checkable certificates. TSP-opt outputs a number, not a yes/no bit — there is no single yes/no answer to certify. Why this step? Membership in NP is a type requirement (decision problem); TSP-opt fails the type before we even ask about certificates.

Verify (small tour). Cities on a unit square, edge weights $=$ Euclidean. The 4 corners $(0, 0), (1, 0), (1, 1), (0, 1)$ : the perimeter tour has length $1 + 1 + 1 + 1 = 4$ ; any tour using a diagonal ( $2 \approx 1.414$ ) plus three sides is longer, e.g. $2 + 1 + 2 + 1 \approx 4.83$ . So $OPT = 4$ . TSP-decision with $k = 4$ says YES, with $k = 3.9$ says NO — a single optimizer answer ( $4$ ) drives both. ✓

Example 5 — Cell E: counting, also wrong type

Example 6 — Cell F: degenerate / trivial inputs

Worked example Does hardness survive empty or fixed instances?

Statement. Examine two boundary inputs of SAT: (a) $ϕ$ with zero clauses; (b) $ϕ$ containing the empty clause. Does NP-hardness of the class hold even though these single instances are trivial?

Forecast: If a specific instance is trivial to solve, does that make the whole problem easy? Guess. (No — hardness is about the whole family, not one input.)

Zero clauses. No constraints, so every assignment works → $ϕ \in$ SAT (satisfiable, vacuously true). Why this step? Confirms the base of the recursion: an empty conjunction is TRUE.
Empty clause present. An empty clause is an OR of nothing = FALSE, which no assignment can satisfy → $ϕ \in /$ SAT. Why this step? Confirms the other extreme: an unsatisfiable-by-construction instance.
Hardness is unaffected. NP-hardness quantifies over all instances; a few easy ones do not lower the worst case. The reduction of Ex 1 still produces hard instances. Why this step? Reminds us "hard" means "no poly algorithm for the whole language," never "every instance is hard."

Verify. Vacuous truth check: an empty conjunction $⋀_{i \in \emptyset} (\cdot) = TRUE$ and an empty disjunction $⋁_{i \in \emptyset} (\cdot) = FALSE$ . So (a) satisfiable, (b) unsatisfiable — the two must give opposite yes/no answers, which they do. ✓

Example 7 — Cell G: real-world word problem

Worked example Exam scheduling as an NP-hard task

Statement. A university has courses that pairwise conflict (some students take both). Assign each course to one of $k$ time slots so no two conflicting courses share a slot. Show this is NP-hard.

Forecast: A scheduling story — which classic hard problem is this in disguise? Guess before step 1. (Graph colouring.)

Model as a graph. Vertex $=$ course; edge $=$ "these two conflict." A valid schedule with $k$ slots $=$ a proper $k$ -colouring (adjacent vertices get different colours/slots). Why this step? Turns fuzzy words into a precise graph object we can reduce with.
Reduce 3-SAT (via known $3-COLOR$ ). Graph 3-colouring is NP-hard (known reduction from 3-SAT). Our scheduling problem with $k = 3$ is 3-colouring → NP-hard by transitivity. Why this step? We land on a textbook-hard target instead of re-deriving from NP.

Verify (tiny schedule). Three courses all pairwise conflicting form a triangle $K_{3}$ . With $k = 2$ slots: try slots ${1, 2}$ — vertex 3 conflicts with both 1 and 2, no free slot → impossible. With $k = 3$ : slots $1, 2, 3$ work. So the answer flips exactly at $k = 3 = χ (K_{3})$ (the chromatic number of a triangle). ✓

Example 8 — Cell H: exam twist (the direction trap)

Worked example Catching a wrong-direction "proof"

Statement. A student claims: "To prove problem $L$ is NP-hard, I reduced $L \leq_{p}$ SAT. Done!" Diagnose the error and state the correct fix.

Forecast: Is $L \leq_{p}$ SAT good news or bad news for proving $L$ hard? Guess. (Bad — it shows $L$ is easy, in NP-ish, the opposite.)

What $L \leq_{p}$ SAT actually proves. It says " $L$ is no harder than SAT" — you can translate $L$ into SAT and solve it there. That is an upper bound on $L$ 's difficulty. Why this step? The arrow $\leq_{p}$ points from easier-or-equal to harder-or-equal: $A \leq_{p} B$ means " $A \leq B$ in difficulty."
What NP-hardness needs. We need $L$ to be at least as hard as everything in NP, i.e. a lower bound. So we must put a known-hard problem on the left: $known-hard \leq_{p} L$ . Why this step? Only "hard flows into $L$ " makes $L$ absorb the hardness.
Correct template. Choose $K \in {$ 3-SAT, CLIQUE, ... $}$ known NP-hard, show $K \leq_{p} L$ . Then $\forall A \in$ NP: $A \leq_{p} K \leq_{p} L$ .

Verify (logic sanity). If $L \leq_{p}$ SAT and SAT $\in$ NP, then $L$ inherits NP membership (assuming $L$ is a decision problem) — literally the opposite of proving $L$ hard. So the student's direction proves easiness, confirming the diagnosis. ✓

Recall Which cell is each poster child in?

HALT lives in cell ::: C (undecidable, NP-hard, not in NP) TSP-optimization lives in cell ::: D (optimization output, wrong type for NP) SAT proven via Cook–Levin lives in cell ::: A (the seed, NP-complete) To prove new $L$ NP-hard you reduce ::: a known-hard problem into $L$ (known-hard $\leq_{p} L$ ), never $L$ into it