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

4.6.27 · Coding › Theory of Computation

Definition mein reductions kyun use hote hain?

Structure ko first principles se derive karna

Hum formalize karna chahte hain ki " $L$ poore class NP se kam-se-kam utna hi hard hai."

" $A$ se kam-se-kam utna hard" ka matlab hona chahiye: $L$ solve karne se $A$ sasta solve ho jaata hai.
Sabse sasta meaningful glue polynomial-time translation hai (taaki hardness dominate kare, translation nahi).
Ek clean translation ek function $f$ hai jo poly time mein computable hai jisme $x \in A ⟺ f (x) \in L .$ Yahi many-one (Karp) reduction $A \leq_{p} L$ hai.
"Har $A \in$ NP se kam-se-kam utna hard" $\Rightarrow$ yeh sab $A \in NP$ ke liye require karo.

Yahi literally NP-hard ki definition hai. Kuch extra (jaise $L \in$ NP) ki zarurat nahi thi — yahi precisely reason hai ki NP-hard NP ke upar stick out kar sakta hai.

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

Reductions compose kaise hote hain (NP-hardness proofs ka engine)

Worked examples

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

Claim: NP ka har $A$ Boolean satisfiability (SAT) mein reduce hota hai. Yeh kyun kaam karta hai (sketch): NP ka koi bhi $A$ ek poly-time verifier $V$ rakhta hai aur ek Turing machine jo use $\leq n^{k}$ steps mein run karti hai. Input $x$ par ek guessed certificate ke saath $V$ ki computation ko ek giant Boolean formula $ϕ_{x}$ ke roop mein likha ja sakta hai jiske variables tape cells aur states ko har time step par encode karte hain, aur clauses "valid transition" aur "accepting" enforce karte hain.

Yeh step kyun? $ϕ_{x}$ ka satisfying assignment = $x$ ke liye accepting certificate, toh $x \in A ⟺ ϕ_{x} \in SAT$ .
Poly time kyun? Tableau $(n^{k}) \times (n^{k})$ cells ka hai, har ek $O (1)$ clauses se describe hota hai → polynomially many clauses. Kyunki poora NP SAT mein reduce hota hai, SAT NP-hard hai. SAT NP mein bhi hai (assignment guess karo, poly time mein check karo) → SAT NP-complete hai.

Worked example 2. Halting Problem NP-hard hai lekin NP mein NAHI

Setup: $HALT = {⟨ M, x ⟩ : M halts on x}$ .

NP-hard? NP ka koi bhi $A$ lo jiske paas poly-time decider-with-cert ho. 3-SAT ko HALT mein reduce karo: ek machine $M_{ϕ}$ banao jo $ϕ$ ke sabhi assignments search karti hai aur tabhi halt karti hai iff koi ek $ϕ$ satisfy karta hai. Phir $ϕ \in 3-SAT ⟺ ⟨ M_{ϕ}, ϵ ⟩ \in HALT$ . $M_{ϕ}$ banana poly time hai. Kyunki 3-SAT NP-hard hai, HALT bhi hai (transitivity).
- Yeh step kyun? Humne "kya koi yes-witness hai" ko "kya yeh searcher kabhi halt karta hai" mein convert kiya.
NP mein? Nahi! HALT undecidable hai (koi algorithm use decide hi nahi kar sakta). Koi decider na hone wale problem ke paas certainly koi poly-time verifier bhi nahi hoga. Toh HALT $\in /$ NP. Conclusion: HALT NP-hard hai lekin NP ke bahar hai — "NP se harder, NP mein nahi bhi ho sakta" ka poster child.

Common mistakes (steel-manned)

Recall Feynman: 12-saal ke bacche ko samjhao

Socho ek classroom mein "NP" naam ke homework problems hain. Ek problem NP-hard hoti hai agar woh ek "master key" ho: agar tum use fast solve kar sako, toh tum us classroom ki har problem quickly solve kar sakte ho — pehle unhe isme translate karke. Lekin surprise yeh hai — master key kisi bilkul alag, aur bhi impossible room ki problem se belong kar sakti hai (jaise "kya yeh computer program kabhi band hoga?"). Woh key NP room kholne ke liye kaafi strong hai, chahe woh khud kahin aur mushkil jagah mein rehti ho. Toh "NP-hard" ka matlab hai poori NP class jitna kam-se-kam tough, iska member hona nahi.

Active-recall flashcards

NP-hard problem ki definition kya hai?

Ek problem

L

jisme har

A \in

NP, polynomial time mein usmein reduce hota hai (

A \leq_{p} L

sabhi

A \in

NP ke liye) — NP ke sab se kam-se-kam utna hi hard.

NP-complete vs NP-hard?

NP-complete = NP-hard AND NP mein; NP-hard akele NP mein membership require nahi karta.

Ek NP-hard problem bataao jo NP mein NAHI hai.

Halting Problem (undecidable, isliye koi poly-time verifier nahi) — ya optimization TSP (decision problem nahi).

Ek NP-hard problem NP mein fail kyun ho sakti hai?

NP ko ek yes/no decision problem chahiye jisme poly-time-checkable certificate ho; NP-hard sirf ek hardness lower bound demand karta hai, toh optimization/undecidable problems hard toh qualify karti hain lekin certificate/type nahi rakhtin.

Ek naya problem

L

NP-hard prove karne ke liye kya karte ho?

Ek KNOWN NP-hard problem

K

L

mein reduce karo (

K \leq_{p} L

); transitivity se poora NP

L

mein reduce ho jaata hai.

NP-hardness prove karne ke liye reduction direction kaun si hai —

L

mein ya

L

se bahar?

L

mein: known-hard

\leq_{p} L

L

ko kisi easy mein reduce karna sirf

L

ki easiness prove karta hai, hardness nahi.

\leq_{p}

ki transitivity state karo aur justify karo.

Agar

A \leq_{p} B

aur

B \leq_{p} C

toh

A \leq_{p} C

h = g \circ f

ke zariye; poly∘poly poly hai aur answers preserve hote hain.

Agar

P = N P

, toh kya sab NP-hard problems poly-time ban jaati hain?

Nahi — sirf woh jo NP mein bhi hain (NP-complete). Undecidable NP-hard problems jaise HALT unsolvable rehti hain.

SAT NP-hard kyun hai?

Cook–Levin: kisi bhi NP machine ki poly-time accepting computation ko ek Boolean formula ke roop mein encode kiya ja sakta hai jo satisfiable hai iff input accept hota hai, poly size mein.

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