NP-complete problems — 3-SAT, Vertex Cover, Clique, Hamiltonian Path, TSP, Subset Sum

4.6.26 · Coding › Theory of Computation

NP-complete kya hai? (3 ingredients)

Reduction tool — Hardness kaise prove karte hain

Cook–Levin theorem (SAT is NP-complete) seed hai: yeh dikhata hai ki har NP problem SAT mein reduce hoti hai, seedha Turing-machine definition se. Uske baad, baaki saari problems ki hardness prove hoti hai pehle se proven NP-complete problem se reduce karke. Classic chain:

$SAT \leq_{p} 3-SAT \leq_{p} Clique \leq_{p} Vertex Cover \leq_{p} Hamiltonian Cycle \leq_{p} TSP$ $3-SAT \leq_{p} Subset Sum$

Figure — NP-complete problems — 3-SAT, Vertex Cover, Clique, Hamiltonian Path, TSP, Subset Sum

Problems ki cast (definitions jo tumhare paas honi chahiye)

Definition Chhe headliners (+1 helper)

3-SAT: CNF mein ek Boolean formula diya gaya hai jahan har clause mein exactly 3 literals hain, kya koi aisa assignment hai jo ise TRUE banaye? e.g. $(x_{1} \lor \neg x_{2} \lor x_{3}) \land (\neg x_{1} \lor x_{2} \lor x_{3})$ .
Clique: Graph $G$ aur integer $k$ diya gaya hai, kya $k$ vertices ka koi set hai jo saare pairwise adjacent hon?
Vertex Cover: $G$ aur $k$ diya gaya hai, kya $k$ vertices ka koi set hai jo every edge ko touch kare?
(helper) Independent Set: vertices ka ek set jisme unke beech koi edge na ho — complement twin jo Clique aur Vertex Cover ko link karta hai.
Hamiltonian Path / Cycle: ek path har vertex ko exactly ek baar visit karta hai; ek cycle bhi yahi karta hai aur start par waapas aata hai.
TSP (decision): weighted complete graph aur budget $B$ diya gaya hai, kya ek aisa tour (cycle) hai jo saare cities ko exactly ek baar visit kare total cost $\leq B$ mein?
Subset Sum: integers $S$ aur target $t$ diye gaye hain, kya koi subset hai jo exactly == $t$ == sum kare?

Derivation 1 — Clique ↔ Vertex Cover ↔ Independent Set (easy trio)

Derivation 2 — 3-SAT $\leq_{p}$ Clique (famous gadget)

Derivation 3 — 3-SAT $\leq_{p}$ Subset Sum (number gadget)

Derivation 4 — Hamiltonian Cycle $\leq_{p}$ TSP

Common mistakes (Steel-man + fix)

Flashcards

NP ka full form aur matlab kya hai?

Nondeterministic Polynomial — ek certificate ko verify kiya ja sake polynomial time mein.

NP-complete define karo.

Ek problem jo NP mein bhi ho aur NP-hard bhi ho (har NP problem poly time mein isme reduce ho).

Problem

B

ko NP-hard prove karne ke liye reduction kis direction mein hogi?

Ek known NP-complete problem

A

B

mein reduce karo:

A \leq_{p} B

A \leq_{p} B

kya guarantee karta hai?

x \in A ⟺ f (x) \in B

jahan

f

poly-time ho;

B

ka fast solver

A

ka bhi fast solver deta hai.

Kaunse theorem ne pehla NP-complete problem establish kiya?

Cook–Levin theorem (SAT is NP-complete).

Independent Set aur Vertex Cover ka relation?

I

size

k

ka independent set

⟺

V ∖ I

size

n - k

ka vertex cover hai.

Clique vs Independent Set ka link?

G

mein Clique

⟺

complement graph

\overset{ˉ}{G}

mein Independent Set.

3-SAT→Clique mein do literal-vertices ke beech edge kab hoti hai?

Alag clauses mein hon AUR ek doosre ke negations na hon; clique size

k = m

Subset Sum ka

O (n t)

DP poly-time algorithm kyun nahi hai?

t

lo g t

bits hain, isliye

t

input length mein exponential ho sakta hai → pseudo-polynomial hai.

HamCycle→TSP mein kaunse edge weights aur budget use hote hain?

Weight 1 real edges ke liye, 2 baaki ke liye; budget

B = ∣ V ∣

(ek tour ek cycle hai jisme

∣ V ∣

edges hain).

TSP budget

∣ V ∣

kyun hai na ki

∣ V ∣ - 1

TSP tour ek cycle hai jo start par waapas aata hai, isliye

∣ V ∣

edges hain, na ki path jaise

∣ V ∣ - 1

Kya NP-complete aur undecidable same hai?

Nahi — NP-complete problems decidable hain (brute force terminate karta hai); bas (likely) poly-time mein nahi.

TSP ka decision form kya hai?

Weighted complete graph aur budget

B

diya gaya ho, kya koi tour (cycle) hai jiska total cost

\leq B

ho?

Recall Feynman: 12-saal ke bacche ko explain karo

Ek bade group ke puzzles imagine karo — Sudoku, mazes, suitcase pack karna. Sab alag dikhte hain, lekin ek secret machine hai jo koi bhi ek puzzle ko doosre mein badal sakti hai. Toh yeh sab really ek hi bada puzzle hain alag-alag disguises mein. Hum inhe jaldi solve karne ka trick nahi jaante, lekin agar tumne ek solve kar liya, toh hum tumhara answer bahut jaldi check kar sakte hain. Aur sabse wild baat: agar kisi ne kabhi sirf ek ka fast trick dhundh liya, toh machine sabka fast trick turant de deti hai. Yeh disguised twins NP-complete kehlaate hain.

Connections

P vs NP — woh open million-dollar question jise yeh problems define karti hain.
Cook–Levin Theorem — saari NP-completeness proofs ka seed.
Polynomial-time Reductions — proof ki machinery.
Boolean Satisfiability (SAT, CNF) — reduction tree ki root.
Graph Theory — Cliques and Independent Sets
Dynamic Programming — Subset Sum / Knapsack (pseudo-polynomial).
Approximation Algorithms — jab exact solve karna hopeless ho toh hum kya karte hain (e.g. 2-approx Vertex Cover).
Undecidability and the Halting Problem — ek zyada strong type ki impossibility.