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

This page assumes you have seen none of the notation on the parent note. We build every symbol, one at a time, each resting on the one before. Return here whenever a symbol on the parent note feels unearned.

0. What a "problem" even means here

Picture a big box labelled with a rule. You drop an input into it, and a single lamp on top lights up: green for YES, red for NO.

Why restrict to yes/no? Because the whole theory compares the difficulty of questions, and yes/no questions are the cleanest unit to compare. A "find the actual answer" task can always be rebuilt out of yes/no questions.

1. The symbol $n$ and the dots $\dots$

The parent writes $x_1,\dots ,x_n$. Read it left to right:

• $x$ with a little number below (a subscript) is just a named slot. $x_1$ is "slot one", $x_2$ is "slot two".
• The three dots $\dots$ mean "keep going the same way".
• $n$ is how many slots there are — it stands for a number we haven't fixed yet.

So $x_1,\dots ,x_n$ is simply: a row of $n$ labelled boxes, and we don't say how many because the argument must work for any number.

2. TRUE / FALSE and the three logic symbols $\wedge \vee \neg$

Each box $x_i$ can hold one of two values: TRUE or FALSE (think: a light switch, ON or OFF). A box holding a truth value is called a Boolean variable (named after George Boole).

Now three operations combine switches. Read each as an everyday word:

Why exactly these three? Because every possible truth-rule you could ever write can be built from just AND, OR, NOT. They are the complete toolkit — so a formula using only them can express any yes/no condition.

So $\varphi$ is a list of demands, all of which must be met simultaneously.

3. What "satisfiable" pictures

The "haystack" from the core idea is now concrete: with $n$ switches there are $2^n$ possible flip-patterns. Checking one pattern is trivial; finding a winning one among $2^n$ is the hard part.

4. Polynomial time — the meaning of "fast"

We keep saying "fast" and "polynomial". Time to earn those words.

Why is polynomial the dividing line between "fast" and "hopeless"? Look at the figure: polynomial curves stay tame; the exponential red curve rockets past them and never comes back. Double the input and $n^2$ merely quadruples, but $2^n$ squares. This is why the whole field draws its line exactly here. See Polynomial-time reduction and P vs NP problem.

5. Certificate, verifier, and the class NP

Here is the subtle one. Some problems we can't solve fast, but if someone hands us the answer, we can check it fast.

Picture a locked door. Finding the key by yourself may take forever, but if a friend hands you a key, testing it in the lock takes one second.

6. Reduction and the symbol ${\le }_p$

Now the machine that transfers hardness between problems.

Why the $\le$ symbol, pointing that way? Because $A{\le }_{p}B$ literally means "$B$ is at least as hard as $A$": if you owned a fast solver for $B$, you could answer any $A$-question by translating it and asking $B$. So difficulty flows uphill toward $B$. This is Polynomial-time reduction.

7. NP-hard, NP-complete — the summit words

SAT is the first proven member (Cook's theorem). From it, Independent Set, Vertex Cover, and Clique inherit NP-completeness by reduction.

The prerequisite map

Read top-down: pictures on the left build formulas; formulas plus timing build the classes P and NP; classes plus reduction feed the summit theorem.

Equipment checklist

Cover the right side and answer aloud before revealing.