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

WHAT are we even talking about?

WHY does Cook's theorem matter? (the 80/20 core)

The 20% you must own: SAT $\in$ NP-complete. Two halves:

SAT $\in$ NP — easy. Given an assignment (the certificate), plug it in and evaluate $\phi$ in poly time. ✔
SAT is NP-hard — the deep part Cook proved: every language $L \in$ NP reduces to SAT.

Once (1)+(2) hold, SAT is the anchor. To prove any new problem $B$ is NP-complete you only do:

Show $B \in$ NP, and
Show some known NP-complete problem $A$ reduces to $B$ ( $A \le_p B$ ).

Because $\le_p$ is transitive, $A \le_p B$ plus "everything $\le_p A$ " gives "everything $\le_p B$ ."

HOW did Cook prove SAT is NP-hard? (derivation from scratch)

Step 1 — The computation tableau

Run $M$ for $p(n)$ steps. The tape never moves beyond cell $p(n)$ . So the whole run is a grid:

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

A $(p(n)+1) \times (p(n)+1)$ tableau. Each cell holds a tape symbol, plus we mark where the head is and what state $M$ is in. Why this step? The entire behaviour of $M$ is captured by this finite grid — finite ⇒ encodable with finitely many Boolean variables.

Step 2 — Boolean variables

For each tableau position $(i,j)$ and each possible content $s$ (a tape symbol, or "head here in state $q$ "), define $x_{i,j,s} = \text{TRUE} \iff \text{cell }(i,j)\text{ has content } s.$ Why? This is the dual coding: a physical configuration ↔ a truth assignment. Number of variables $= O(p(n)^2)\cdot(\text{constant alphabet}) =$ polynomial. ✔

Step 3 — Clauses enforce "this is a legal accepting run"

We AND together clauses of four types:

Why the $2\times3$ window for moves? The Turing head only affects the cell under it and its neighbours in one step. So legality is a local property: if every little window is locally legal, the whole run is legal. This locality is what keeps the formula size polynomial.

Step 4 — Wrap up

Total clauses: $O(p(n)^2)$ , each of constant size. Building $\phi_{M,w}$ takes polynomial time in $|w|$ . ✔
$\phi_{M,w}$ satisfiable $\iff$ a legal accepting tableau exists $\iff$ $M$ accepts $w$ $\iff$ $w\in L$ .

So $L \le_p \text{SAT}$ for every $L\in$ NP. Combined with SAT $\in$ NP: SAT is NP-complete. $\blacksquare$

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

WHY reductions go "the right way" (the #1 confusion)

To prove B is NP-hard, reduce a known-hard $A$ into $B$ : build $f$ with $x\in A \iff f(x)\in B$ .

Worked example Worked reduction: 3-SAT

$\le_p$ Independent Set Goal: show Independent Set (IS) is NP-hard using 3-SAT. Input: 3-SAT formula, $m$ clauses each with 3 literals, e.g. $(x_1\vee \neg x_2\vee x_3)\wedge(\neg x_1\vee x_2\vee x_4)$ . Construction $f$ :

For each clause make a triangle of 3 vertices (one per literal). Why? A triangle forces an independent set to pick at most ONE vertex per clause = choosing one literal to satisfy that clause.
Add an edge between any two vertices that are complementary literals ( $x_i$ and $\neg x_i$ ). Why? This forbids choosing a literal and its negation simultaneously — keeps the truth assignment consistent.
Set target $k = m$ (number of clauses). Claim: $\phi$ satisfiable $\iff$ graph has independent set of size $m$ .
( $\Rightarrow$ ) A satisfying assignment makes $\ge 1$ literal true per clause; pick one true literal per triangle → $m$ vertices, no two adjacent. Why no edge? Same clause excluded by triangle; complementary excluded because both can't be true.
( $\Leftarrow$ ) An IS of size $m$ hits each triangle exactly once; set those literals TRUE → consistent (no complementary pair) and satisfies every clause. $f$ is clearly poly-time. Hence IS is NP-hard, and since IS $\in$ NP, IS is NP-complete. ✔

Common mistakes (Steel-manned)

Active recall

Recall Test yourself (cover the answers)

What two things must you prove for "X is NP-complete"? → $X\in$ NP and $X$ is NP-hard.
Direction to prove B is NP-hard? → known NPC $A \le_p B$ (reduce from A to B).
What does Cook's reduction encode as Boolean variables? → the contents of each tableau cell at each time step.
Why is the move-clause only over a $2\times3$ window? → head changes are local, so legality is checkable locally.
SAT $\in$ NP — what's the certificate? → a truth assignment; verify by evaluating $\phi$ .

What does NP stand for and mean

Nondeterministic Polynomial — "yes" instances have a certificate verifiable in poly time.

Definition of NP-complete

A problem that is both in NP and NP-hard.

Definition of NP-hard

Every problem in NP reduces to it in polynomial time (at least as hard as all of NP).

State Cook's theorem

SAT (Boolean satisfiability) is NP-complete.

Two parts to proving SAT is NP-complete

(1) SAT ∈ NP via evaluating an assignment; (2) SAT is NP-hard by reducing every NP language to SAT.

Core idea of Cook's reduction

Encode a nondeterministic TM's accepting computation tableau as a Boolean formula satisfiable iff the machine accepts.

What do variables x_{i,j,s} mean in Cook's proof

Cell (i,j) of the tableau at time i, position j contains content s (true/false).

The four clause groups in Cook's formula

cell (exactly one content), start (correct initial row), accept (some accepting state appears), move (every 2×3 window is a legal transition).

Why are move-clauses over local windows

TM head changes only affect a cell and its neighbours per step, so legality is a local property.

Meaning of A ≤_p B

Poly-time f with x∈A ⟺ f(x)∈B; B is at least as hard as A.

To prove B is NP-hard, which direction reduce

Reduce a known NP-complete A TO B (A ≤_p B), not the reverse.

Why is reducing B to SAT wrong for hardness

It only shows B is no harder than SAT, not that B is hard.

Reduction 3-SAT ≤_p Independent Set: clause gadget

A triangle of 3 vertices (one per literal), forcing ≤1 chosen per clause.

Reduction 3-SAT ≤_p IS: consistency edges

Edges between complementary literals x and ¬x to forbid contradictory choices.

In 3-SAT ≤_p IS, what target size k

k = number of clauses m.

Is P ⊆ NP

Yes — anything solvable in poly time is trivially verifiable in poly time.

Why ≤_p transitivity matters

It lets new NP-completeness proofs chain off one anchor (SAT) instead of re-reducing all of NP.

Recall Feynman: explain to a 12-year-old

Imagine a giant lock factory making thousands of different tricky locks (hard puzzles). Cook found ONE special master key (SAT) that can open every lock the factory makes. So if you ever invent a super-fast way to copy that master key, you instantly open all the locks. And to prove a new lock is also super-tricky, you just show "this new lock can be shaped to act like the master key" — that means it's tricky too. The trick to building the master key was writing down the whole step-by-step diary of a guessing-robot solving a puzzle, as one giant true/false riddle: the riddle is solvable exactly when the robot can win.

Connections

P vs NP problem — Cook's theorem is the foundation of this open question.
Polynomial-time reduction — the tool that propagates hardness.
3-SAT — restricted SAT, also NP-complete via clause splitting.
Karp's 21 NP-complete problems — the first wave of reductions from SAT.
Turing machine / Nondeterministic Turing machine — the computation model encoded in the tableau.
Independent Set / Vertex Cover / Clique — classic graph NP-complete trio.
Verifier definition of NP — gives the certificate view used for "SAT ∈ NP".

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Dekho, idea simple hai par powerful. NP ka matlab hai aise problems jinka answer "haan" ho to uska certificate (ek guessed solution) hum poly-time me verify kar sakte hain. SAT ek aisi problem hai: ek Boolean formula do, kya koi true/false assignment hai jo use TRUE bana de? Cook ne prove kiya ki SAT NP-complete hai — yaani SAT NP me hai aur NP ki har problem SAT me reduce ho jaati hai. Matlab SAT ek "master key" hai: agar SAT fast solve ho gaya, to poori NP fast solve ho jaayegi.

Cook ka jugaad genius hai. Koi bhi NP problem lo — uske liye ek nondeterministic Turing machine hai jo poly steps me accept karti hai. Cook us machine ke poore computation ko ek tableau (grid: rows = time, columns = tape cells) ke roop me likhte hain, aur har cell ke content ko Boolean variable bana dete hain. Phir clauses lagao: har cell ka exactly ek content ho, row 0 sahi start ho, kahin accepting state aaye, aur har $2\times3$ window legal transition follow kare (kyunki TM ka head local change karta hai). Yeh formula tabhi satisfiable hoga jab machine accept karti hai. Bas — har NP problem SAT me reduce ho gayi.

Ab sabse important practical baat: reduction ki direction. Kisi nayi problem $B$ ko NP-hard prove karna ho to ek already-known hard problem $A$ ko $B$ me reduce karo, yaani $A \le_p B$ . Galat tareeka hai $B$ ko SAT me daalna — usse sirf yeh sabit hota hai ki $B$ SAT se zyada hard nahi, jo hum chahte hi nahi. Slogan yaad rakho: "famous hard problem se reduce karo, apni nayi problem ki taraf." Jaise 3-SAT $\le_p$ Independent Set me har clause ka ek triangle banate hain aur complementary literals ke beech edge daalte hain.

Yeh matter isliye karta hai kyunki ek baar SAT anchor mil gaya, aur reductions transitive hote hain, to naye NP-complete problems prove karna sasta ho gaya — poori NP dobara reduce karne ki zaroorat nahi. Yahi P vs NP question ki foundation hai.

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

WHAT are we even talking about?

WHY does Cook's theorem matter? (the 80/20 core)

HOW did Cook prove SAT is NP-hard? (derivation from scratch)

Step 1 — The computation tableau

Step 2 — Boolean variables

Step 3 — Clauses enforce "this is a legal accepting run"

Step 4 — Wrap up

WHY reductions go "the right way" (the #1 confusion)

Common mistakes (Steel-manned)

Active recall

Connections

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — Theory of Computation

Connections