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

WHY does the definition use reductions?

Deriving the structure from first principles

We want to formalize " $L$ is at least as hard as the whole class NP."

"At least as hard as $A$ " should mean: solving $L$ gives solving $A$ cheaply.
The cheapest meaningful glue is polynomial-time translation (so the hardness, not the translation, dominates).
A clean translation is a function $f$ computable in poly time with $x \in A \iff f(x) \in L.$ This is the many-one (Karp) reduction $A \le_p L$ .
"At least as hard as every $A\in$ NP" $\Rightarrow$ require this for all $A \in \text{NP}$ .

That literally is the definition of NP-hard. Nothing extra (like $L\in$ NP) was needed — which is precisely why NP-hard can stick out above NP.

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

HOW reductions compose (the engine of NP-hardness proofs)

Worked examples

Worked example 1. SAT is NP-hard (Cook–Levin, the seed)

Claim: Every $A\in$ NP reduces to Boolean satisfiability (SAT). Why this works (sketch): Any $A\in$ NP has a poly-time verifier $V$ and a Turing machine running it in $\le n^k$ steps. The computation of $V$ on input $x$ with a guessed certificate can be written as a giant Boolean formula $\phi_x$ whose variables encode the tape cells and states at each time step, with clauses enforcing "valid transition" and "accepting."

Why this step? A satisfying assignment of $\phi_x$ = an accepting certificate for $x$ , so $x\in A \iff \phi_x \in \text{SAT}$ .
Why poly time? The tableau is $(n^k)\times(n^k)$ cells, each described by $O(1)$ clauses → polynomially many clauses. Since all NP reduces to SAT, SAT is NP-hard. SAT is also in NP (guess assignment, check in poly time) → SAT is NP-complete.

Worked example 2. The Halting Problem is NP-hard but NOT in NP

Setup: $\text{HALT}=\{\langle M,x\rangle : M \text{ halts on } x\}$ .

NP-hard? Take any $A\in$ $A \in$ NP with poly-time decider-with-cert. Reduce 3-SAT to HALT: build a machine $M_\phi$ $M_{ϕ}$ that searches all assignments of $\phi$ $ϕ$ and halts iff one satisfies $\phi$ $ϕ$ . Then $\phi\in\text{3-SAT}\iff \langle M_\phi,\epsilon\rangle\in\text{HALT}$ $ϕ \in 3-SAT ⟺ ⟨ M_{ϕ}, ϵ ⟩ \in HALT$ . Building $M_\phi$ $M_{ϕ}$ is poly time. Since 3-SAT is NP-hard, so is HALT (transitivity).
- Why this step? We turned "is there a yes-witness" into "does this searcher ever halt."
In NP? No! HALT is undecidable (no algorithm decides it at all). A problem with no decider certainly has no poly-time verifier. So HALT $\notin$ NP. Conclusion: HALT is NP-hard yet sits outside NP — the poster child for "harder than NP, may not be in NP."

Common mistakes (steel-manned)

Recall Feynman: explain to a 12-year-old

Imagine a classroom of homework problems called "NP." A problem is NP-hard if it's a "master key": if you could solve it fast, you could quickly solve every problem in that classroom by first translating them into it. But here's the surprise — the master key might belong to a problem from a totally different, even more impossible room (like "will this computer program ever stop?"). It's a key strong enough to open the NP room, even if it itself lives somewhere harder. So "NP-hard" means at least as tough as the whole NP class, not "a member of it."

Active-recall flashcards

What is the definition of an NP-hard problem?

A problem

L

such that every

A\in

NP reduces to it in polynomial time (

A\le_p L

for all

A\in

NP) — at least as hard as all of NP.

NP-complete vs NP-hard?

NP-complete = NP-hard AND in NP; NP-hard alone does not require membership in NP.

Give an NP-hard problem that is NOT in NP.

The Halting Problem (undecidable, hence no poly-time verifier) — or optimization TSP (not a decision problem).

Why can an NP-hard problem fail to be in NP?

NP needs a yes/no decision problem with a poly-time-checkable certificate; NP-hard only demands a hardness lower bound, so optimization/undecidable problems qualify as hard but lack the certificate/type.

To prove a new problem

L

is NP-hard, what do you do?

Reduce a KNOWN NP-hard problem

K

L

(

K\le_p L

); by transitivity all of NP reduces to

L

Which reduction direction proves NP-hardness — into or out of

L

INTO

L

: known-hard

\le_p L

. Reducing

L

into something easy proves

L

is easy, not hard.

State and justify transitivity of

\le_p

A\le_p B

and

B\le_p C

then

A\le_p C

, via

h=g\circ f

; poly∘poly is poly and answers are preserved.

P=NP

, do all NP-hard problems become poly-time?

No — only those also in NP (NP-complete). Undecidable NP-hard problems like HALT stay unsolvable.

Why is SAT NP-hard?

Cook–Levin: any NP machine's poly-time accepting computation can be encoded as a Boolean formula satisfiable iff input is accepted, in poly size.

Connections

NP-complete — NP-hard and in NP
Cook–Levin Theorem
Polynomial-time many-one reduction
Class NP — verifier and certificate definition
Halting Problem — undecidability
P vs NP
3-SAT and reduction templates
Decision vs Optimization problems

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Dekho, NP-hard ka matlab hai: ek problem jo NP class ke har problem se kam se kam utni hi mushkil hai. Formally, agar koi $A \in$ NP hai, to use polynomial time mein hamari problem $L$ mein convert (reduce) kar sakte hain. Iska seedha matlab — agar $L$ fast solve ho jaye, to poori NP class fast solve ho jaye. Isliye $L$ ek "master key" jaisa hai.

Ab twist yahan hai: NP-hard hone ke liye $L$ ka NP mein hona zaroori nahi. NP mein hone ke liye problem decision (haan/naa) type honi chahiye aur uska ek chhota certificate poly time mein verify hona chahiye. Lekin NP-hard sirf "neeche se bound" deta hai (kam se kam itni hard). Isliye Halting Problem (jo undecidable hai, koi algorithm hi nahi) ya optimization TSP (jo decision problem hi nahi) — ye NP-hard hain par NP ke bahar baithe hain. Yahi line yaad rakho: "harder than NP, may not be in NP."

Proof technique simple hai aur yahi 80/20 hai: naya problem $L$ NP-hard sabit karne ke liye poori NP ko dobara reduce mat karo — bas ek already-known NP-hard problem (jaise 3-SAT) ko $L$ mein reduce karo: $K \le_p L$ . Transitivity ki wajah se $A \le_p K \le_p L$ , to saari NP automatically $L$ mein chali gayi. Direction yaad rakhna: known-hard ko $L$ ke andar daalo, ulta nahi — warna tum galti se $L$ ko easy sabit kar doge.

Yaad rakhne ka mantra: "All complete are hard; not all hard are complete." NP-complete = NP-hard + NP mein. NP-hard akela = difficulty ka floor, jo upar undecidable tak ja sakta hai.

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

WHAT is NP-hard?

WHY does the definition use reductions?

Deriving the structure from first principles

HOW reductions compose (the engine of NP-hardness proofs)

Worked examples

Common mistakes (steel-manned)

Active-recall flashcards

Connections

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — Theory of Computation

Connections