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

Before we start, fix the vocabulary in one picture. The figure below draws NP as the blue oval (problems with a short certificate), NP-hard as the pink dashed region stretching off to the right and upward (the floor of difficulty — reduction arrows point into it), and their overlap as NP-complete (yellow). Notice SAT sits in the yellow overlap, while HALT and optimization-TSP are drawn as dots outside the blue oval but still inside the pink region — that is the entire point of this page: NP-hard reaches beyond NP.

Figure — NP-hard — harder than NP, may not be in NP

Recall The three words you must never confuse

In NP = a yes/no problem with a short certificate you can check fast (the blue oval).
NP-hard = everything in NP reduces into you (the pink floor); reduction arrows point toward you.
NP-complete = both at once (the yellow overlap). Reduction direction ::: To prove $L$ hard you show known-hard $\leq_{p} L$ (arrow into $L$ ), never $L \leq_{p}$ known-hard.

Level 1 — Recognition

Recall Solution L1.1

a) TRUE. NP-complete $=$ NP-hard $AND$ in NP, so the NP-hard part is included by definition. b) FALSE. NP-hardness is only a lower bound; it never forces membership. (Halting Problem is the counterexample.) c) TRUE. The why: you take a known NP-hard problem (3-SAT) and build, in poly time, a machine $M_{ϕ}$ that halts iff $ϕ$ is satisfiable — giving $3-SAT \leq_{p} HALT$ . Because 3-SAT is NP-hard, transitivity makes HALT NP-hard too. (The full construction of that machine is exercise L4.1; here we only assert it exists.) d) TRUE. This is literally the definition of NP-complete.

Recall Solution L1.2

(i) Eligible — yes/no answer, certificate = the cycle. (ii) Ineligible — it outputs a number, not a yes/no. (Optimization; can still be NP-hard.) (iii) Eligible — yes/no, certificate = the assignment. (iv) Ineligible — it outputs a count, not a yes/no. (Counting problem, class #P.)

Rule of thumb: if the answer is a bit (yes/no), it can live in NP; if the answer is a number, it cannot — see Decision vs Optimization problems.

Level 2 — Application

Recall Solution L2.1

A reduction $L \leq_{p} 3-SAT$ means: a fast solver for 3-SAT gives a fast solver for $L$ . That shows $L$ is no harder than 3-SAT — informally it hints $L$ might be in NP, the opposite of hardness. To prove $L$ is NP-hard you need the arrow the other way: $3-SAT \leq_{p} L,$ i.e. a fast solver for $L$ gives a fast solver for 3-SAT. Then, since 3-SAT is NP-hard, transitivity gives $A \leq_{p} 3-SAT \leq_{p} L$ for every $A \in$ NP, so $L$ is NP-hard.

Recall Solution L2.2

Take any $A \in$ NP. Because 3-SAT is NP-hard, $A \leq_{p} 3-SAT$ . Chain the reductions: $A \leq_{p} 3-SAT \leq_{p} CLIQUE \leq_{p} VERTEX-COVER .$ Transitivity of $\leq_{p}$ (proved in the parent) collapses this chain to $A \leq_{p} VERTEX-COVER$ . Since $A$ was arbitrary in NP, every NP problem reduces to VERTEX-COVER, so VERTEX-COVER is NP-hard. $□$

Note we only ever built one new reduction ( $3-SAT \leq_{p} CLIQUE$ ); the rest is bookkeeping.

Recall Solution L2.3

Step 1 — run $f$ : time $\leq 3 n^{2}$ , and output size $∣ f (x) ∣ \leq 3 n^{2}$ (can't write more symbols than time steps). Step 2 — run $g$ on that output of size $m \leq 3 n^{2}$ : time $\leq 5 m^{3} \leq 5 (3 n^{2})^{3} = 5 \cdot 27 n^{6} = 135 n^{6}$ . Total: $3 n^{2} + 135 n^{6} = O (n^{6})$ — a polynomial. So $h$ is a valid poly-time reduction. This is why "polynomial composed with polynomial is polynomial" matters.

Level 3 — Analysis

Recall Solution L3.1

(a) NP-hard. Decision-TSP ("is there a tour of length $\leq k$ ?") is NP-complete, hence NP-hard. Suppose you had a fast solver $OPT$ for optimization-TSP that returns the minimum tour length $ℓ^{*}$ . Then to answer decision-TSP with bound $k$ : run $OPT$ , and answer yes iff $ℓ^{*} \leq k$ . That is a poly-time reduction $decision-TSP \leq_{p} optimization-TSP$ . Since decision-TSP is NP-hard, so is optimization-TSP. (b) Not in NP. NP is a class of decision (yes/no) languages. Optimization-TSP outputs a number, so it is not even the right type of object — there is no single bit answer to certify. Hence it cannot be in NP regardless of how easy or hard it is. (See Decision vs Optimization problems.)

Recall Solution L3.2

(a) SAT becomes solvable in polynomial time. SAT is NP-complete, so it is in NP; if $P = N P$ then everything in NP (including SAT) is in P. See P vs NP. (b) HALT is unaffected — it stays undecidable. $P = N P$ only says "the NP class equals the P class." HALT is NP-hard but not in NP (it isn't even decidable), so collapsing NP onto P touches nothing about HALT. No amount of $P$ -vs- $N P$ news gives you an algorithm that doesn't exist. Moral: $P = N P$ helps exactly the NP-hard problems that are also in NP (the NP-complete ones).

Recall Solution L3.3

$L_{2}$ is NP-complete, so it is in NP; being in NP and $L_{1}$ NP-hard gives $L_{2} \leq_{p} L_{1}$ . Symmetrically $L_{1} \in$ NP and $L_{2}$ NP-hard give $L_{1} \leq_{p} L_{2}$ . So both directions hold — all NP-complete problems are inter-reducible. But $\leq_{p}$ is not symmetric in general. Example: any $A \in P$ reduces to 3-SAT ( $A \leq_{p} 3-SAT$ , trivially by solving $A$ during the reduction), yet $3-SAT \leq_{p} A$ would put an NP-hard problem inside P, unknown/false unless $P = N P$ . The mutual reducibility above is a special feature of NP-completeness, not of $\leq_{p}$ .

Level 4 — Synthesis

Recall Solution L4.1

Construction. Given a 3-CNF formula $ϕ$ with $n$ variables, output the description of a machine $M_{ϕ}$ that ignores its input and does:

Enumerate all $2^{n}$ truth assignments $a_{1}, a_{2}, \dots$ in order.
For each, evaluate $ϕ$ (poly time per assignment).
If some $a_{i}$ satisfies $ϕ$ : halt. If it exhausts all assignments: enter an infinite loop (while true: skip).

The figure below traces this: the blue box is the input $ϕ$ , the yellow arrow is the poly-time build step, and the pink box is the machine $M_{ϕ}$ whose behaviour splits into "halt" or "loop forever." Read the equivalence line under it.

Equivalence. If $ϕ$ is satisfiable, step 3 finds a satisfying $a_{i}$ and halts → $⟨ M_{ϕ}, ϵ ⟩ \in$ HALT. If $ϕ$ is unsatisfiable, no assignment triggers the halt, so $M_{ϕ}$ loops forever → $\in /$ HALT. Thus $ϕ \in 3-SAT ⟺ ⟨ M_{ϕ}, ϵ ⟩ \in$ HALT. Poly-time. We are only writing down the code of $M_{ϕ}$ (embedding $ϕ$ 's clauses as constants). The description length is linear in $∣ ϕ ∣$ ; we never run $M_{ϕ}$ . So the reduction $f (ϕ) = ⟨ M_{ϕ}, ϵ ⟩$ is poly-time — even though $M_{ϕ}$ itself may run forever.

Key subtlety we exploited: the reduction converts "does a witness exist?" into "does this searcher ever stop?" — turning search into halting.

Recall Solution L4.2

Problem: $MAX-SAT-VALUE$ = "given a CNF formula $ϕ$ , output the maximum number of clauses simultaneously satisfiable."

NP-hard: From its answer you can decide "can all $m$ clauses be satisfied?" (i.e. SAT) by checking if the output equals $m$ . That is a poly-time reduction $SAT \leq_{p} MAX-SAT-VALUE$ , and SAT is NP-hard.
Not in NP: It outputs a number, not yes/no, so it is not a decision language — ineligible for NP, just like optimization-TSP.

(Another valid answer: the counting problem $# SAT$ = "how many satisfying assignments?" — NP-hard, not a decision problem, hence not in NP.)

Level 5 — Mastery

Recall Solution L5.1

Step (1) is correct (that reduction is exactly L4.1). Step (2) is wrong, and here is precisely why:

The trace of a halting computation can be exponentially (or unboundedly) long — there is no polynomial bound on the number of steps before $M$ halts. A certificate for NP must have length polynomial in the input size; a trace violates that.
Even worse, for a non-halting input there is no finite trace at all to reason about, and no bound tells the verifier when to give up. This is exactly why HALT is undecidable — Turing's diagonal argument shows no algorithm (hence no poly-time verifier) decides it. Correct conclusion: HALT is NP-hard but not in NP, therefore not NP-complete. It is the canonical "harder than NP, not in NP" example. See Halting Problem — undecidability.

Recall Solution L5.2

Problem: $TRUE-QBF$ = "is this fully-quantified Boolean formula $\forall x_{1} \exists x_{2} \forall x_{3} \dots ψ$ true?" (Quantified SAT / TQBF).

Decidable: finitely many variables → brute force over all assignments decides it. So unlike HALT, it has an algorithm.
NP-hard: 3-SAT is the special case where all quantifiers are $\exists$ ( $\exists x_{1} \dots \exists x_{n} ϕ$ ). That is an immediate reduction $3-SAT \leq_{p} TRUE-QBF$ , so TRUE-QBF is NP-hard.
Believed not in NP: TQBF is PSPACE-complete. If it were in NP, then every problem in PSPACE would also be in NP: any PSPACE problem $B$ satisfies $B \leq_{p} TQBF$ (TQBF is PSPACE-hard), and composing that reduction with TQBF's assumed NP-membership would put $B$ in NP too — forcing $NP = PSPACE$ . Since $NP = PSPACE$ is widely conjectured false (it would collapse the polynomial hierarchy), TQBF is believed not to be in NP. So under standard assumptions TRUE-QBF is NP-hard, decidable, yet outside NP.

This fills the last cell of the map: NP-hard problems can be (i) in NP [NP-complete], (ii) decidable but likely above NP [TQBF], or (iii) undecidable [HALT].

Recall One-line map of everything above

NP-hard = floor of difficulty. On that floor you find: NP-complete (in NP, e.g. SAT), decidable-but-above-NP (e.g. TQBF, PSPACE-complete), and undecidable (e.g. HALT). Membership in NP is a separate question decided by "is there a short, poly-checkable certificate?"