On the previous page, we drew hard lines: some problems are undecidable, period. We proved this using reductions — showing that if you could solve problem B, you could solve the known-undecidable problem A. But those reductions had no concern for efficiency. A computable function that takes a trillion years is still a valid mapping reduction.
Now we shift the question. We're no longer asking "can this be computed at all?" — we're asking "can this be computed efficiently?" This is the transition from computability theory to complexity theory. And the tool that lets us compare efficiency between problems is the polynomial-time reduction.
But first, we need to formalize what we already used informally on the undecidability page: mapping reductions. Then we'll define "efficient" (the class P), define "efficiently verifiable" (the class NP), and build the machinery to ask the most famous open question in computer science: is P = NP?
Before we get to efficiency, let's formalize the reduction technique we used throughout the undecidability chapter. Every proof there had the same shape: "assume B is decidable, use it to decide the known-undecidable A, contradiction." The tool that connects A to B is a mapping reduction.
Imagine you have a nightclub (problem B) with a bouncer who perfectly decides who gets in. You want to figure out whether someone is on the VIP list for a different club (problem A). If you can disguise any person from A's list so that the B-bouncer accepts them if and only if they'd be accepted at A — then B's bouncer is effectively solving A's problem. The disguise function is the reduction.
The key property: \(f\) must map yes-instances of A to yes-instances of B, AND no-instances of A to no-instances of B. It's a perfect disguise — it never introduces false positives or false negatives.
Recall from the undecidability page: to prove \(E_{\text{TM}}\) is undecidable, we showed that if we could decide emptiness, we could decide acceptance. Let's restate that as a formal mapping reduction to the complement of \(E_{\text{TM}}\):
Define \(f(\langle M, w \rangle)\) = \(\langle M_1 \rangle\), where \(M_1\) is a TM that does:
\(M_1 = \) "On input \(x\): if \(x \neq w\), reject. If \(x = w\), run \(M\) on \(w\) and accept if \(M\) accepts."
Why this works:
The function \(f\) is computable (it just constructs a TM description), and \(\langle M, w \rangle \in A_{\text{TM}} \iff f(\langle M, w \rangle) \in \overline{E_{\text{TM}}}\). Therefore \(A_{\text{TM}} \leq_m \overline{E_{\text{TM}}}\).
The same reduction also gives us \(\overline{A_{\text{TM}}} \leq_m E_{\text{TM}}\) (note the complements flip):
Use the same function \(f(\langle M, w \rangle) = \langle M_1 \rangle\) as above.
Mapping reductions transfer decidability and recognizability downward (from the target to the source), and undecidability upward (from the source to the target):
Let \(R\) be a decider for \(B\) and \(f\) the reduction from \(A\) to \(B\). Build a decider for \(A\):
"On input \(w\): compute \(f(w)\), then run \(R\) on \(f(w)\). Accept if \(R\) accepts; reject if \(R\) rejects."
This always halts (both \(f\) and \(R\) are computable/total), and it's correct because \(w \in A \iff f(w) \in B\).
Think of it like a dependency graph in your codebase. If service B has no bugs (decidable), and your adapter function (reduction) works correctly, then service A has no bugs either. Conversely, if service A has a bug (undecidable), and the adapter works correctly, then B must have a bug too — the bug must come from somewhere.
Before we can talk about "efficient" computation, we need to agree on what counts as the size of an input. This seems obvious — but it's the source of the single most common mistake in complexity theory.
The key detail: the bound only needs to hold eventually. We get to choose both the constant \(c\) and the starting point \(n_0\). This means Big-O ignores constant factors and lower-order terms — it captures the growth rate.
When we say "the running time of an algorithm is \(O(n^2)\)," \(n\) is the length of the input encoding — the number of bits (or symbols) needed to write down the input. For most data structures, this is intuitive:
That last one is the trap.
Consider these two Python functions:
Function A runs in \(O(n)\) time where \(n\) is the input size — the loop count is proportional to the number of list elements, which is proportional to the encoding size.
Function B also looks like it runs in \(O(x)\) time. But \(x\) is not the input size! The integer \(x\) is encoded in \(n = O(\log x)\) bits. So \(x = 2^{O(n)}\), and the loop runs \(O(2^n)\) times — exponential in the input size.
The classic Knapsack problem has a well-known \(O(|S| \cdot W)\) dynamic programming solution. Is Knapsack in P?
No — at least, this algorithm doesn't prove it. The weight capacity \(W\) is a number, encoded in \(\log W\) bits. The algorithm runs \(W\) iterations, which is \(2^{\log W}\) — exponential in the encoding length. An algorithm that is polynomial in the numeric value of the input but exponential in the encoding length is called pseudo-polynomial.
Now we can define "efficient computation." The idea: a problem is "tractable" if a deterministic Turing machine can solve it in time bounded by a polynomial in the input size.
P captures the problems we consider "tractable" in practice. Why polynomial? Because polynomial-time algorithms compose polynomially (we'll use this later), and because the Strong Church-Turing Thesis says: anything your laptop solves in polynomial time, a TM can solve in polynomial time too.
| Problem | Algorithm | Running time |
|---|---|---|
| \(A_{\text{DFA}}\) — does DFA \(B\) accept \(w\)? | Simulate \(B\) on \(w\) | \(O(|w|)\) on a real computer; polynomial on a single-tape TM |
| PATH — is there a path from \(s\) to \(t\) in graph \(G\)? | BFS or DFS | \(O(|V| + |E|)\) |
| Shortest Path | Dijkstra's algorithm | \(O((|V| + |E|) \log |V|)\) |
| Sorting | Merge sort | \(O(n \log n)\) |
| \(\Sigma^*\) (accept everything) | Immediately accept | \(O(1)\) — in \(\text{TIME}(1) \subseteq P\) |
| \(\{w \mid w = a^*\}\) (all a's) | Scan and check each symbol | \(O(n)\) — in \(\text{TIME}(n) \subseteq P\) |
Consider these variations on graph path problems, all on undirected graph \(G = (V, E)\):
| Problem | In P? | Why |
|---|---|---|
| Simple path from \(s\) to \(t\) visiting all vertices in alphabetical order | Yes | Unique candidate path — just check if edges exist. \(O(|V|)\) |
| Simple path visiting all vertices exactly once (HAMP) | No* | NP-complete — no known polynomial algorithm |
| Simple path from \(s\) to \(t\) with weight \(\geq K\) | No* | Longest path — NP-hard |
*Assuming P ≠ NP.
Some problems seem hard to solve but easy to check. Finding a Hamiltonian path in a graph? Nobody knows a fast algorithm. But if someone hands you a path, you can verify it visits every vertex exactly once in linear time. This "easy to check" property defines NP.
The two definitions are equivalent: the NDTM's nondeterministic choices encode the certificate, and the verification is the deterministic check on that branch.
Consider this paragraph:
Without context, this is incomprehensible. But if I give you the certificate — "kite-flying" — suddenly every sentence makes perfect sense, and you can verify the fit instantly. That's the P vs. NP gap: understanding with a certificate is easy; discovering the answer from scratch may be hard.
The Hamiltonian Path problem: given an undirected graph \(G = (V, E)\), is there a simple path that visits every vertex exactly once?
Certificate: A sequence of vertices \((v_1, v_2, \ldots, v_{|V|})\) — the proposed path.
Verifier \(V\): On input \(\langle G, (v_1, \ldots, v_{|V|}) \rangle\):
Running time: Steps 1–3 are all \(O(|V| + |E|)\). The certificate is polynomial in size (\(|V|\) vertex names). So the verifier runs in polynomial time.
"Nondeterministically pick a starting vertex. Then nondeterministically pick an unvisited neighbor. Repeat until all vertices are visited. If successful, accept."
Each nondeterministic choice is \(O(1)\), we make \(|V|\) choices, and the final verification is \(O(|V|)\). Total: polynomial nondeterministic time.
Real-world analogy: You're placing security cameras at intersections. Each camera covers all roads meeting at that intersection. Can you cover every road segment with at most \(K\) cameras?
Certificate: A set of vertices \(V'\) with \(|V'| \leq K\).
Verifier: Check \(|V'| \leq K\). Then for each edge \(\{u,v\} \in E\), check that \(u \in V'\) or \(v \in V'\). All in \(O(|V| + |E|)\).
Real-world analogy: In a social network, a clique is a group of people who are all mutual friends. Can you find such a group of size at least \(K\)?
Certificate: A set of vertices \(V'\) with \(|V'| \geq K\).
Verifier: Check \(|V'| \geq K\). Then for each pair \(u, v \in V'\) with \(u \neq v\), check that \(\{u,v\} \in E\). This takes \(O(K^2) \leq O(|V|^2)\) — polynomial.
We know:
┌─────────────────────────────────────────────┐
│ EXP │
│ ┌─────────────────────────────────┐ │
│ │ NP │ │
│ │ ┌─────────────────────┐ │ │
│ │ │ P │ │ │
│ │ │ PATH, A_DFA, │ │ │
│ │ │ Sorting, ... │ HAMP? │ │
│ │ └─────────────────────┘ │ │
│ └─────────────────────────────────┘ │
└─────────────────────────────────────────────┘
P ⊆ NP ⊆ EXP P ⊂ EXP (strict)
P = NP ???
Why it matters beyond CS:
If P = NP, all of these "verifying is easier" intuitions would be wrong. Every verification procedure could be turned into a construction procedure with only polynomial overhead.
Mapping reductions (\(\leq_m\)) asked only that the function \(f\) be computable — it could take exponential time or worse. For complexity theory, we need a tighter version: the reduction itself must be efficient.
Every Karp reduction is a mapping reduction. Not every mapping reduction is a Karp reduction (the function might take too long). Karp reductions are the "polynomial-time mapping reductions" — same structure, stricter time budget.
Why do polynomial-time reductions matter? Because polynomial composed with polynomial is still polynomial.
Given input \(w\) of size \(n\):
Total: \(O(n^d) + O(n^{dc}) = O(n^{dc})\). A polynomial of a polynomial is still a polynomial.
This is the key property. It means: if \(A \leq_p B\) and \(B \in P\), then \(A \in P\). Polynomial-time solvability transfers downward through Karp reductions, just like decidability transfers through mapping reductions.
Two problems on directed graphs:
We have a solver for DPATH (BFS). Can we use it to solve DCYCLE?
On input \((V, E, s)\), construct \((V', E', s', t')\):
All outgoing edges from \(s\) now leave from \(s'\). All incoming edges to \(s\) now arrive at \(t'\).
Correctness: A cycle through \(s\) in \(G\) corresponds to a path from \(s'\) to \(t'\) in \(G'\), and vice versa.
Time: The transformation is \(O(|V| + |E|)\) — linear, clearly polynomial.
Karp reductions classify problems by difficulty:
This is the foundation for NP-completeness: finding the hardest problems in NP.
Some problems in NP seem harder than others. HAMP, SAT, CLIQUE, VERTEX COVER — nobody has found polynomial-time algorithms for any of them, despite decades of effort. Are they the same kind of hard? Yes — they are all NP-complete.
NP-hard (extends beyond decidable!)
┌─────────────────────────────────────────
│
│ ┌───────── Decidable ────────┐
│ │ ┌──────── NP ───────┐ │
│ │ │ ┌───────────┐ │ │
│ │ │ │ P │ │ │
│ │ │ └───────────┘ │ │
│ │ │ [NPC] │ │ ← NP ∩ NP-hard
│ │ └───────────────────┘ │
│ └─────────────────────────┘
│
│ A_TM (undecidable, but NP-hard!)
│
Suppose some problem \(X\) is in both NPC and P. Take any \(A \in NP\).
This is the reason NP-completeness matters. A polynomial-time algorithm for any single NPC problem would collapse the entire P vs NP divide. Conversely, proving any NPC problem has no polynomial algorithm would prove P ≠ NP.
The definitions above are useless without an actual NPC problem. How do you prove something is NP-hard — that every NP problem reduces to it? You'd need to handle infinitely many problems. This seems impossible, but Stephen Cook (1971) and Leonid Levin (independently, 1973) found a way.
A SAT instance in conjunctive normal form (CNF) looks like:
$$\underbrace{(u \lor x \lor \neg z)}_{\text{clause 1}} \;\land\; \underbrace{(\neg u \lor \neg y)}_{\text{clause 2}} \;\land\; \underbrace{(u \lor \neg x \lor y \lor \neg z)}_{\text{clause 3}} \;\land\; \underbrace{(\neg u \lor \neg y \lor \neg z)}_{\text{clause 4}}$$Try \(\tau = \{u = 1, x = 1, y = 0, z = 0\}\):
| Clause | Substitution | Result |
|---|---|---|
| \(u \lor x \lor \neg z\) | \(1 \lor 1 \lor 1\) | 1 |
| \(\neg u \lor \neg y\) | \(0 \lor 1\) | 1 |
| \(u \lor \neg x \lor y \lor \neg z\) | \(1 \lor 0 \lor 0 \lor 1\) | 1 |
| \(\neg u \lor \neg y \lor \neg z\) | \(0 \lor 1 \lor 1\) | 1 |
All clauses satisfied. This is a yes-instance of SAT.
3SAT is a special case of SAT (every 3SAT instance is a SAT instance). Despite the restriction, 3SAT is still NP-complete — proven by reducing general SAT to 3SAT (splitting long clauses with fresh variables). 3SAT is the standard starting point for NPC reductions because its fixed clause size simplifies constructions.
Certificate: A truth assignment \(\tau: U \to \{0, 1\}\).
Verifier: For each clause (exactly 3 literals), check that at least one literal is true. Each clause check is \(O(1)\); total is \(O(|C|)\). Polynomial.
The proof shows that for any language \(L \in NP\), there is a polynomial-time reduction from \(L\) to SAT. The idea:
The proof is not trivial (Sipser devotes several pages to it), but the core idea is beautiful: any NDTM computation can be "compiled" into a Boolean formula. If you can solve SAT, you can simulate any nondeterministic polynomial-time computation.
Once you have one NPC problem (SAT, via Cook-Levin), you can prove others NPC without repeating the Cook-Levin construction. The recipe:
Why does step 2 work? If \(Y\) is NPC, then every NP problem reduces to \(Y\). If \(Y \leq_p X\), then by transitivity every NP problem reduces to \(X\). So \(X\) is NP-hard.
The chain of reductions typically starts from SAT or 3SAT:
Each arrow is a Karp reduction. The L15 lecture covers the VC, CLIQUE, and HAMP reductions in detail.
SAT is a decision problem: it answers "yes" or "no." But in practice, you don't just want to know whether a satisfying assignment exists — you want to find one. Can a decision oracle help?
Yes. SAT is self-reducible: if you have a fast SAT decider, you can find a satisfying assignment with only a polynomial number of calls to the decider.
Given: A SAT decider \(D\) (runs in \(O(1)\) for simplicity) and instance \((U, C)\).
Step 1: Call \(D(U, C)\). If "no," return null (unsatisfiable).
Step 2: For each variable \(u \in U\):
Step 3: Return \(\tau\).
Instance: \(U = \{a, b\}\), \(C = \{(a \lor b),\; (\neg a \lor b)\}\).
Step 1: \(D(U, C)\) = yes. Proceed.
Step 2, variable \(a\):
Step 2, variable \(b\):
Result: \(\tau = \{a = 0, b = 1\}\). Verify: \((0 \lor 1) = 1\) ✓, \((1 \lor 1) = 1\) ✓. Correct!
Running time: The loop runs \(|U|\) times. Each iteration does \(O(|C|)\) clause manipulation plus one \(O(1)\) decider call. Total: \(O(|U| \cdot |C|)\) — polynomial. Even if the decider ran in \(O(n^k)\), the total would be \(O(n^{k+1})\) — still polynomial.
| Concept | Definition | Key fact |
|---|---|---|
| \(A \leq_m B\) | Computable \(f\) with \(w \in A \iff f(w) \in B\) | Transfers decidability/recognizability |
| \(A \leq_p B\) | Polynomial-time \(f\) with \(w \in A \iff f(w) \in B\) | Transfers P membership |
| P | \(\bigcup_k \text{TIME}(n^k)\) | Efficiently solvable |
| NP | \(\bigcup_k \text{NTIME}(n^k)\) = poly-time verifiable | \(P \subseteq NP \subseteq EXP\) |
| NP-hard | \(\forall Y \in NP: Y \leq_p X\) | Can extend beyond Decidable (\(A_{\text{TM}}\)!) |
| NPC | \(NP \cap \text{NP-hard}\) | If any NPC problem is in P, then P = NP |
| SAT | Boolean satisfiability | First known NPC problem (Cook-Levin) |
| 3SAT | SAT with exactly 3 literals per clause | Also NPC; standard starting point for reductions |