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

What is NP-complete? (the 3 ingredients)

The reduction tool — HOW we prove hardness

Cook–Levin theorem (SAT is NP-complete) is the seed: it shows every NP problem reduces to SAT directly from the Turing-machine definition. After that, all other problems are proven hard by reducing from an already-proven NP-complete problem. The classic chain:

$\text{SAT} \le_p \text{3-SAT} \le_p \text{Clique} \le_p \text{Vertex Cover} \le_p \text{Hamiltonian Cycle} \le_p \text{TSP}$ $\text{3-SAT} \le_p \text{Subset Sum}$

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

The cast of problems (definitions you must own)

Definition The six headliners (+1 helper)

3-SAT: Given a Boolean formula in CNF where each clause has exactly 3 literals, is there an assignment making it TRUE? e.g. $(x_1 \lor \lnot x_2 \lor x_3)\land(\lnot x_1 \lor x_2 \lor x_3)$ .
Clique: Given graph $G$ and integer $k$ , is there a set of $k$ vertices all pairwise adjacent?
Vertex Cover: Given $G$ and $k$ , is there a set of $k$ vertices touching every edge?
(helper) Independent Set: a set of vertices with no edge between them — the complement twin that links Clique and Vertex Cover.
Hamiltonian Path / Cycle: a path visits every vertex exactly once; a cycle does the same and returns to the start.
TSP (decision): given weighted complete graph and budget $B$ , a tour (cycle) visiting all cities exactly once with total cost $\le B$ ?
Subset Sum: given integers $S$ and target $t$ , a subset summing to exactly == $t$ ==?

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

Formula The duality identity (derived, not memorized)

Let $I$ = independent set, $C = V\setminus I$ . $I \text{ is independent of size } k \iff C \text{ is a vertex cover of size } n-k.$ And $I$ is independent in $G$ $\iff$ $I$ is a clique in the complement graph $\bar G$ (flip every edge). Therefore: $G \text{ has clique } \ge k \iff \bar G \text{ has independent set } \ge k \iff \bar G \text{ has vertex cover } \le n-k.$

Derivation 2 — 3-SAT $\le_p$ Clique (the famous gadget)

Formula The construction

Given 3-SAT formula with $m$ clauses:

Make a vertex for each literal in each clause → $3m$ vertices, grouped in $m$ triples.
Put an edge between two vertices $u,v$ iff they are in different clauses AND are not negations of each other ( $x$ vs $\lnot x$ blocked).
Set $k = m$ . Claim: $\;\text{formula satisfiable} \iff G$ has a clique of size $m$ .

WHY ( $\Rightarrow$ ): pick one true literal per clause. They're in different clauses (edges exist) and can't be $x$ & $\lnot x$ since both can't be true → all pairwise connected → clique of size $m$ . WHY ( $\Leftarrow$ ): a size- $m$ clique must use one vertex from each clause (no edges inside a clause). Set those literals true; consistency is guaranteed because contradicting pairs have no edge → valid assignment.

Derivation 3 — 3-SAT $\le_p$ Subset Sum (number gadget)

Derivation 4 — Hamiltonian Cycle $\le_p$ TSP

Formula Construction (cycle ↔ tour, so the edge counts match)

Given graph $G=(V,E)$ for Hamiltonian Cycle, $n=|V|$ . Build the complete graph on $V$ with weights: $w(u,v) = \begin{cases} 1 & (u,v)\in E\\ 2 & \text{otherwise}\end{cases}$ Set budget $B = n$ . WHY $n$ (not $n-1$ ): a TSP tour is a cycle visiting all $n$ vertices and returning to start, so it uses exactly $n$ edges. The cheapest possible such cycle costs $\ge n$ (every edge $\ge 1$ ), and costs exactly $n$ $\iff$ all $n$ edges have weight $1$ $\iff$ they are all real edges of $G$ $\iff$ $G$ has a Hamiltonian cycle. $G \text{ has a Hamiltonian cycle} \iff \text{TSP tour of cost} \le n \text{ exists.}$

Common mistakes (Steel-man + fix)

Flashcards

What does NP stand for and mean?

Nondeterministic Polynomial — a certificate can be verified in polynomial time.

Define NP-complete.

A problem that is both in NP and NP-hard (every NP problem reduces to it in poly time).

To prove problem

B

is NP-hard, which direction is the reduction?

Reduce a known NP-complete problem

A

into

B

A \le_p B

What does

A \le_p B

guarantee?

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

with

f

poly-time; a fast solver for

B

gives one for

A

Which theorem first established an NP-complete problem?

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

Relation between Independent Set and Vertex Cover?

I

independent of size

k

\iff

V\setminus I

is a vertex cover of size

n-k

Clique vs Independent Set link?

Clique in

G

\iff

Independent Set in complement graph

\bar G

In 3-SAT→Clique, when is there an edge between two literal-vertices?

Different clauses AND not negations of each other; clique size

k=m

Why isn't Subset Sum's

O(nt)

DP a poly-time algorithm?

t

has

\log t

bits, so

t

can be exponential in input length → pseudo-polynomial.

In HamCycle→TSP, what edge weights and budget are used?

Weight 1 for real edges, 2 otherwise; budget

B=|V|

(a tour is a cycle with

|V|

edges).

Why is the TSP budget

|V|

and not

|V|-1

A TSP tour is a cycle returning to start, so it has

|V|

edges, not

|V|-1

like a path.

Is NP-complete the same as undecidable?

No — NP-complete problems are decidable (brute force terminates); just (likely) not poly-time.

Decision form of TSP?

Given weighted complete graph and budget

B

, is there a tour (cycle) of total cost

\le B

Recall Feynman: explain to a 12-year-old

Imagine a huge group of puzzles — Sudoku, mazes, packing suitcases. They all look different, but there's a secret machine that can turn any one puzzle into any other. So they're really one giant puzzle in disguises. We don't know a quick trick to solve them, but if you finish one, we can check your answer super fast. And the wild part: if someone ever finds a fast trick for just one, the machine instantly gives a fast trick for all of them. These disguised twins are called NP-complete.

Connections

P vs NP — the open million-dollar question these problems define.
Cook–Levin Theorem — the seed of all NP-completeness proofs.
Polynomial-time Reductions — the proof machinery.
Boolean Satisfiability (SAT, CNF) — root of the reduction tree.
Graph Theory — Cliques and Independent Sets
Dynamic Programming — Subset Sum / Knapsack (pseudo-polynomial).
Approximation Algorithms — what we do when exact is hopeless (e.g. 2-approx Vertex Cover).
Undecidability and the Halting Problem — a stronger kind of impossibility.

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Dekho, NP-complete problems basically ek hi gang ke members hain jo alag-alag costume pehne hue hain. 3-SAT, Clique, Vertex Cover, Hamiltonian Cycle/Path, TSP, Subset Sum — yeh sab apparently bohot hard lagte hain (koi fast solution nahi pata), par inki ek khaas baat hai: agar koi tumhe answer de de, to tum usse polynomial time mein verify kar sakte ho. Isi ko NP kehte hain — "verify karna easy, dhoondhna hard". Aur NP-complete matlab yeh NP ke andar ke sabse hard problems hain. (Independent Set ek helper twin hai jo Clique aur Vertex Cover ko jodta hai.)

Asli jaadu hai reduction. Reduction ek fast translator hai: $A \le_p B$ ka matlab — agar $B$ ka fast solver mil jaaye, to $A$ bhi fast solve ho jaayega. Toh hardness prove karne ka rule yaad rakho: naye problem $B$ ko hard dikhane ke liye, kisi already-known hard problem ko $B$ ke andar feed karo. Direction ulta mat karna — yeh sabse common galti hai! Cook–Levin theorem ne sabse pehle SAT ko NP-complete prove kiya, aur baaki sab usi se chain banake prove hue.

Ek important trap: Subset Sum ka $O(n \cdot t)$ DP dekh ke lagta hai "are yeh to polynomial hai!" — par nahi. Target $t$ ek number hai jiski length sirf $\log t$ bits hai, toh $t$ input ke size mein exponential ho sakta hai. Isko pseudo-polynomial kehte hain. Aur ek aur dhyaan dene wali baat — TSP ka tour ek cycle hota hai (start pe wapas aata hai), isliye usme $n$ edges hote hain, $n-1$ nahi. Isiliye HamCycle→TSP reduction mein budget $B=n$ rakhte hain, $n-1$ nahi. Yeh poora khel P vs NP ke million-dollar question ke center mein hai, aur NP-complete ka matlab undecidable nahi — yeh solve to ho jaate hain brute force se, bas fast nahi.

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

What is NP-complete? (the 3 ingredients)

The reduction tool — HOW we prove hardness

The cast of problems (definitions you must own)

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

Derivation 2 — 3-SAT $\le_p$ Clique (the famous gadget)

Derivation 3 — 3-SAT $\le_p$ Subset Sum (number gadget)

Derivation 4 — Hamiltonian Cycle $\le_p$ TSP

Common mistakes (Steel-man + fix)

Flashcards

Connections

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — Theory of Computation

Connections