NP-completeness — Cook's theorem (SAT is NP-complete), reduction

4.6.25 · Coding › Theory of Computation

KISKE baare mein baat kar rahe hain hum?

Cook's theorem KYUN matter karta hai? (80/20 core)

Woh 20% jo aapko pakka pata hona chahiye: SAT $\in$ NP-complete. Do hissay:

SAT $\in$ NP — aasaan. Ek assignment (certificate) diya, usse plug in karo aur $ϕ$ ko poly time mein evaluate karo. ✔
SAT is NP-hard — woh deep part jo Cook ne prove kiya: NP ka har language $L \in$ NP, SAT mein reduce hota hai.

Jab (1)+(2) hold ho jaayein, SAT anchor ban jaata hai. Kisi bhi nayi problem $B$ ko NP-complete prove karne ke liye bas:

Dikhao $B \in$ NP, aur
Dikhao koi jaana-maana NP-complete problem $A$ , $B$ mein reduce hota hai ( $A \leq_{p} B$ ).

Kyunki $\leq_{p}$ transitive hai, $A \leq_{p} B$ plus "sab kuch $\leq_{p} A$ " se milta hai "sab kuch $\leq_{p} B$ ."

Cook ne SAT ko NP-hard KAISE prove kiya? (scratch se derivation)

Step 1 — Computation tableau

$M$ ko $p (n)$ steps tak run karo. Tape kabhi bhi cell $p (n)$ se aage nahi jaati. Toh poora run ek grid hai:

	cell 0	cell 1
time 0	...	...
time 1	...	...
...
time $p (n)$

Ek $(p (n) + 1) \times (p (n) + 1)$ tableau. Har cell mein ek tape symbol hota hai, saath mein hum mark karte hain kahan head hai aur $M$ kis state mein hai. Yeh step kyun? $M$ ka poora behaviour is finite grid mein capture ho jaata hai — finite ⇒ finitely many Boolean variables se encode ho sakta hai.

Step 2 — Boolean variables

Har tableau position $(i, j)$ aur har possible content $s$ (ek tape symbol, ya "head yahan state $q$ mein hai") ke liye define karo $x_{i, j, s} = TRUE ⟺ cell (i, j) has content s .$ Kyun? Yeh dual coding hai: ek physical configuration ↔ ek truth assignment. Variables ki sankhya $= O (p (n)^{2}) \cdot (constant alphabet) =$ polynomial. ✔

Step 3 — Clauses "yeh ek legal accepting run hai" ko enforce karte hain

Hum four types ke clauses AND karke jodte hain:

Moves ke liye $2 \times 3$ window kyun? Turing head ek step mein sirf apne neeche wale cell aur uske neighbours ko affect karta hai. Toh legality ek local property hai: agar har chhota window locally legal hai, toh poora run legal hai. Yahi locality formula size ko polynomial rakhti hai.

Step 4 — Wrap up

Total clauses: $O (p (n)^{2})$ , har ek constant size ka. $ϕ_{M, w}$ banana $∣ w ∣$ mein polynomial time leta hai. ✔
$ϕ_{M, w}$ satisfiable $⟺$ ek legal accepting tableau exist karta hai $⟺$ $M$ , $w$ ko accept karta hai $⟺$ $w \in L$ .

Toh $L \leq_{p} SAT$ NP ke har $L \in$ NP ke liye. SAT $\in$ NP ke saath milake: SAT is NP-complete. $■$

Figure — NP-completeness — Cook's theorem (SAT is NP-complete), reduction

Reductions "sahi direction" mein KYUN jaate hain (sabse #1 confusion)

B ko NP-hard prove karne ke liye, ek jaane-maane-hard $A$ ko B mein reduce karo: ek $f$ banao jisme $x \in A ⟺ f (x) \in B$ .

Worked example Worked reduction: 3-SAT

$\leq_{p}$ Independent Set Goal: 3-SAT use karke dikhao ki Independent Set (IS) NP-hard hai. Input: 3-SAT formula, $m$ clauses har ek mein 3 literals, jaise $(x_{1} \lor \neg x_{2} \lor x_{3}) \land (\neg x_{1} \lor x_{2} \lor x_{4})$ . Construction $f$ :

Har clause ke liye 3 vertices ka ek triangle banao (ek har literal ke liye). Kyun? Triangle force karta hai ki independent set ek clause mein at most ONE vertex choose kare = us clause ko satisfy karne ke liye ek literal chunna.
Koi bhi do vertices jo complementary literals hain ( $x_{i}$ aur $\neg x_{i}$ ) unke beech ek edge daalo. Kyun? Yeh ek literal aur uske negation ko simultaneously choose karne se rokta hai — truth assignment consistent rakhta hai.
Target $k = m$ (clauses ki sankhya) set karo. Claim: $ϕ$ satisfiable $⟺$ graph mein $m$ size ka independent set hai.
( $\Rightarrow$ ) Ek satisfying assignment har clause mein $\geq 1$ literal true banata hai; har triangle se ek true literal chuno → $m$ vertices, koi do adjacent nahi. Koi edge kyun nahi? Same clause triangle se exclude; complementary exclude kyunki dono ek saath true nahi ho sakte.
( $\Leftarrow$ ) $m$ size ka ek IS har triangle ko exactly ek baar hit karta hai; un literals ko TRUE set karo → consistent (koi complementary pair nahi) aur har clause satisfy hota hai. $f$ clearly poly-time hai. Isliye IS is NP-hard, aur IS $\in$ NP hone se, IS is NP-complete. ✔

Common mistakes (Steel-manned)

Active recall

Recall Khud test karo (jawaab chhupa ke)

"X is NP-complete" ke liye kya do cheezein prove karni hain? → $X \in$ NP aur $X$ NP-hard hai.
B ko NP-hard prove karne ki direction? → known NPC $A \leq_{p} B$ ( $A$ se B mein reduce karo).
Cook's reduction mein Boolean variables kya encode karte hain? → har time step par har tableau cell ka content.
Move-clause sirf $2 \times 3$ window par kyun hai? → head changes local hote hain, toh legality locally checkable hai.
SAT $\in$ NP — certificate kya hai? → ek truth assignment; $ϕ$ evaluate karke verify karo.

NP ka matlab aur definition kya hai

Nondeterministic Polynomial — "yes" instances ka ek certificate poly time mein verifiable hota hai.

NP-complete ki definition

Ek problem jo NP mein bhi hai aur NP-hard bhi.

NP-hard ki definition

NP ka har problem usmein polynomial time mein reduce hota hai (NP ke sabse mushkil ke barabar).

Cook's theorem batao

SAT (Boolean satisfiability) NP-complete hai.

SAT ko NP-complete prove karne ke do parts

(1) SAT ∈ NP via ek assignment evaluate karke; (2) SAT is NP-hard by NP ke har language ko SAT mein reduce karke.

Cook's reduction ka core idea

Ek nondeterministic TM ke accepting computation tableau ko ek Boolean formula ke roop mein encode karo jo satisfiable ho tabhi jab machine accept kare.

Cook's proof mein variables x_{i,j,s} ka matlab

Tableau ka cell (i,j) time i par, position j par content s contain karta hai (true/false).

Cook's formula mein chaar clause groups

cell (exactly one content), start (sahi initial row), accept (koi accepting state appear ho), move (har 2×3 window ek legal transition hai).

Move-clauses local windows par kyun hain

TM head ek step mein sirf ek cell aur uske neighbours ko affect karta hai, toh legality ek local property hai.

A ≤_p B ka matlab

Poly-time f aisa ki x∈A ⟺ f(x)∈B; B kam se kam A jitna mushkil hai.

B ko NP-hard prove karne ke liye kis direction mein reduce karo

Ek known NP-complete A ko B MEIN reduce karo (A ≤_p B), ulta nahi.

B ko SAT mein reduce karna hardness ke liye kyun galat hai

Yeh sirf dikhata hai B SAT se zyada mushkil nahi, yeh nahi ki B hard hai.

Reduction 3-SAT ≤_p Independent Set: clause gadget

3 vertices ka ek triangle (ek literal per), har clause se ≤1 choose karne ko force karta hai.

Reduction 3-SAT ≤_p IS: consistency edges

Complementary literals x aur ¬x ke beech edges taaki contradictory choices forbidden ho.

3-SAT ≤_p IS mein target size k kya hai

k = clauses ki sankhya m.

Kya P ⊆ NP hai

Haan — jo bhi poly time mein solvable hai woh trivially poly time mein verifiable bhi hai.

≤_p transitivity kyun matter karta hai

Yeh nayi NP-completeness proofs ko ek anchor (SAT) se chain karne deta hai instead of NP ke poore ko re-reduce karne ke.

Recall Feynman: 12-saal ke bacche ko samjhao

Socho ek giant lock factory hazaaron alag-alag tricky locks (mushkil puzzles) banati hai. Cook ne ek special master key (SAT) dhundhi jo factory ke saare locks khol sakti hai. Toh agar aap kabhi is master key ko super-fast copy karne ka tarika invent karo, toh turant saare locks khul jaate hain. Aur yeh prove karne ke liye ki koi nayi lock bhi super-tricky hai, bas dikhao "yeh nayi lock master key jaisi act kar sakti hai" — matlab woh bhi tricky hai. Master key banane ki trick thi ki ek guessing-robot ke puzzle solve karne ke poore step-by-step diary ko ek giant true/false riddle ke roop mein likhna: riddle tabhi solve hota hai jab robot jeet sakta hai.

Connections

P vs NP problem — Cook's theorem is sahare sawaal ki neenv hai.
Polynomial-time reduction — woh tool jo hardness propagate karta hai.
3-SAT — restricted SAT, clause splitting se bhi NP-complete.
Karp's 21 NP-complete problems — SAT se reductions ki pehli wave.
Turing machine / Nondeterministic Turing machine — tableau mein encode hone wala computation model.
Independent Set / Vertex Cover / Clique — classic graph NP-complete trio.
Verifier definition of NP — "SAT ∈ NP" ke liye use hone wala certificate view.