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

We build from absolute zero. If you have never seen an arrow like ${\le }_p$, a symbol like $⟺$, or the word "graph" used to mean dots-and-lines — you are in exactly the right place. Nothing below is assumed; everything is earned.

Layer 0 — The pictures we draw everything on

A graph (dots and lines)

The picture is everything here. Look at the figure: the blue dots are $V$, the white lines are $E$. When the parent note says "graph $G$ and integer $k$", it is handing you a picture like this plus a number.

Why the topic needs this: every graph problem (Clique, Vertex Cover, Hamiltonian, TSP) is a question about which dots to pick or which lines to walk. No graph vocabulary → no way to even state the problems.

$|V|$ and $n$ — counting the dots

Picture: just point at the dots and say "one, two, three... $n$."

Layer 1 — Sets, and the symbols that move things between them

Look at the figure: the whole rectangle is $V$, the shaded blob is $I$, and $V\setminus I$ is everything left over. When the parent proves "$I$ independent $⟺V\setminus I$ is a vertex cover", it is literally saying "shade a blob, and what's left has a special property." You must be able to see that leftover region.

Why the topic needs it: a "solution" to these problems is almost always a chosen subset of vertices — a blob inside the picture. Complement lets us flip between "the blob" and "everything else", which is the entire trick of Derivation 1.

Layer 2 — Logic symbols (the language of SAT)

Before any graph, the seed problem is about true/false logic. We need its alphabet.

The figure shows two little truth tables — the complete behaviour of OR and AND, all cases. Read every row: OR has just one FALSE row (both off); AND has just one TRUE row (both on). There are no other cases to worry about — two inputs, two values each, four rows, done.

Why the topic needs it: 3-SAT — the ancestor of the whole family via Cook–Levin Theorem — is stated entirely in these symbols. See Boolean Satisfiability (SAT, CNF) for the full treatment.

Layer 3 — The "there exists / for all" quantifiers

Picture: $\exists$ is you finding one working key on a keyring; $\forall$ is you checking that every key on the ring has some property. "Is the formula satisfiable?" means "$\exists$ a switch-setting making it true?". "Vertex cover" asks that $\forall$ edges are touched.

Layer 4 — The arrows that glue statements together

Picture: $\Rightarrow$ is a one-way street; $⟺$ is a two-way street. When the parent proves a reduction it always proves an $⟺$ — a perfect two-way translation, never a leaky one-way one.

Why the topic needs it: the definition of a reduction is literally an $⟺$ (Layer 6). Miss the two-way-ness and you'll accept broken reductions.

Layer 5 — "Fast": polynomial time and $O(\cdot )$

Look at the figure: polynomial curves ($n$, $n^2$) crawl; the exponential curve ($2^n$) rockets off the chart. That gap is the P-vs-NP drama — see P vs NP. "Fast" lives in the crawling zone.

Layer 6 — The reduction arrow ${\le }_p$ and its two definitions

Now every piece is on the table, so we can finally read the topic's key notation.

The map shows the flow: pure sets + logic + counting at the top feed the two engines — graph problems and 3-SAT — and the arrows + fast-time notions build the reduction machine that welds the whole family into one. See Polynomial-time Reductions for the machinery and Graph Theory — Cliques and Independent Sets for the graph side. Everything ultimately loops back to the parent: the NP-complete topic.

A tiny worked check (tying symbols to a picture)

Equipment checklist

Read each question, answer in your head, then reveal.