NP-Completeness

By the end of this lesson you will be able to say exactly what P, NP and co-NP mean, why complexity theory talks about yes/no (decision) problems, how a fast verifier checks a certificate for Hamiltonian cycle, CLIQUE, subset sum and 3SAT, and how each classic polynomial-time reduction — circuit satisfiability → SAT → 3SAT → CLIQUE → vertex cover, vertex cover → Hamiltonian cycle (with its 12-vertex widget), Hamiltonian cycle → TSP and 3SAT → subset sum — transforms one problem into another. Every reduction is animated step by step and computed live from an instance you can edit, and each one is checked against a brute-force search (YES ⇔ YES, NO ⇔ NO). This lesson is theory: the pictures are walkthroughs of constructions, not pseudocode runs. It builds on growth of functions (what "polynomial" means), graph basics (vertices, edges, paths) and dynamic programming (the subset-sum table and Held-Karp).

Polynomial time, decision problems, encodings, P

Think of a jigsaw puzzle. If a friend hands you a finished puzzle, you can check it in a minute by glancing at the picture. Solving it from a bag of loose pieces may take hours. Complexity theory asks: which problems are easy to solve (class P), and which are at least easy to check once somebody gives you the answer (class NP)?

An algorithm runs in polynomial time if its number of steps is O(n^c) for some constant c, where n is the size of the input (how many symbols it takes to write it down). Polynomials are the standard "tractable" yardstick because sums, products and compositions of polynomials are polynomials: chaining a polynomial number of polynomial-time steps stays polynomial.

Abstract problems and decision problems. A problem is a relation from instances to solutions. The lesson restricts to decision problems, whose answer is just YES/NO, because they are easier to compare. We lose nothing important: an optimization problem ("find the largest clique", "find the cheapest tour") is turned into a decision problem by adding a bound ("is there a clique of size ≥ k?", "is there a tour of cost ≤ k?"). If the decision problem is easy, so is the optimization problem (binary-search or step through k, see the first animation); if the optimization problem is easy, its decision version is trivially easy. So a decision problem is at most as hard as the optimization problem it comes from.

Encodings. A concrete problem is a decision problem whose instances are binary strings, so "size" is well defined. Reasonable encodings (a graph as an adjacency matrix or list, numbers in binary) differ from each other only by a polynomial, so the choice does not change whether something is polynomial. One important warning: writing a number n in unary takes n symbols, in binary only ⌊lg n⌋ + 1. An algorithm that is polynomial in the value of a number (like the subset-sum table later) is only pseudo-polynomial — exponential in the bit length.

The class P is the set of languages (sets of YES instances) decidable in polynomial time. Examples in P: "does this graph have a path of length ≤ k between s and t?" (BFS), "is this list sorted?", "is this 2-CNF formula satisfiable?". Not known to be in P: Hamiltonian cycle, CLIQUE, subset sum, 3SAT.

Tiny example. Four towns A, B, C, D with roads A–B, B–C, C–D and A–C. Optimization question: "what is the largest group of towns that are all joined to each other?" (answer 3: A, B, C). Decision questions: "is there such a group of size ≥ 3?" YES; "of size ≥ 4?" NO. Asking the decision question for k = 1, 2, 3, 4 recovers the optimization answer, which is exactly what the first animation does with a yes/no oracle.

Watch out: "optimization vs decision" only compares problems up to polynomial factors. Never say "TSP is in NP"; say "the decision version TSP(G, c, k) is in NP". The optimization version is not a yes/no question, so it is not even in the running for the class NP.

Why polynomial is the yardstick. Sums, products and compositions of polynomials are polynomials (see growth of functions), so "polynomial time" does not care which reasonable machine model or encoding you pick, and chained algorithms stay polynomial. It is not a promise of speed (n¹⁰⁰ is polynomial), but every known exponential-time problem eventually beats every polynomial, and in practice natural problems that are in P get small exponents. Numbers written in unary are the exception that proves the rule: unary blows the input size up to the value itself, which is why "polynomial in the value" only counts as pseudo-polynomial.

P = YES/NO problems solvable in time O(n^c), n = input length in bits. Optimization problems become decision problems by adding a bound (k). The decision version is never harder than the optimization version.

Polynomial closure as code. A running time p(n) = c₀ + c₁n + c₂n² + … is its coefficient list; sums, products and compositions of such lists are again lists, and degrees add or multiply. A reduction that takes q(n) steps and hands a q(n)-symbol instance to a p-step algorithm costs q(n) + p(q(n)) — still a polynomial:

Encodings as code. A number n takes n symbols in unary but only ⌊lg n⌋ + 1 in binary. The subset-sum table below is polynomial in the value t, and the step counter shows each extra bit of t doubling the work (pseudo-polynomial):

Decision versus optimization as code. The largest clique from yes/no answers: ask k = 1, 2, … (at most n calls) or binary-search k (about lg n calls, because "is there a clique of size ≥ k?" only ever flips from yes to no once); the optimum in turn answers every decision question:

Input size → what's feasible. instances of a few hundred symbols are what the exact solvers here handle: a clique oracle by brute force costs 2ⁿ subsets (n ≤ 20 ⇒ 10⁶), the subset-sum table n·t (n = 200, t = 10⁵ ⇒ 2·10⁷ steps) and the polynomial-algebra helpers are instant; the certificate checkers above scale to 10⁵–10⁶ symbols.

Polynomial-time verification: the class NP (and co-NP)

A Sudoku grid that someone claims is solved: checking 27 rows, columns and boxes is fast, while finding the solution may be hard. The claimed solution is a certificate (a proof that the answer is YES), and the checking routine is a verifier.

A verification algorithm A takes two inputs: an instance x and a certificate y. It accepts the pair when y proves that x is a YES instance. The language verified by A is {x : there exists a certificate y with A(x, y) = accept}. NP is the class of languages verified by a polynomial-time algorithm using a polynomial-size certificate (the name means nondeterministic polynomial time: a machine that could guess the certificate). Two facts:

P ⊆ NP: if you can decide x in polynomial time, the verifier can ignore the certificate and just decide.
Nobody knows whether P = NP. Most researchers believe P ≠ NP, but this is the biggest open problem in the field.

co-NP is the class of languages whose complement is in NP: L ∈ co-NP means "NO answers of L have short, checkable certificates" (the complement of SAT is UNSAT, where "unsatisfiable" is hard to certify briefly). Facts: P ⊆ NP ∩ co-NP; if NP ≠ co-NP then P ≠ NP; it is open whether NP = co-NP. Relations known as a picture: P sits inside NP ∩ co-NP, which sits inside NP and co-NP; the NP-complete problems (below) lie in NP but, unless NP = co-NP, outside co-NP.

Tiny example. Instance: S = {2, 3, 7}, target t = 10. Certificate: the chosen numbers {3, 7}. Verifier: 3 + 7 = 10, accept. Finding {3, 7} means trying subsets (there are 2³ = 8); checking it takes one addition.

Three classic slips. (1) NP does not mean "not polynomial"; it means "nondeterministic polynomial", and every problem in P is in NP. (2) A verifier that rejects a certificate y only says "y is not a witness", it does not prove that x is a NO instance; that is why NO answers of SAT have no known short proof (UNSAT ∈ co-NP, not known to be in NP). (3) The certificate must be polynomially short; a certificate of exponential length could not even be read in polynomial time.

Where the word "nondeterministic" comes from. Imagine a machine that at every step may choose between several next moves and accepts if some sequence of choices accepts. "Guessing the certificate" is such a choice sequence, and checking the guess is the deterministic verifier. Both definitions of NP describe the same class. Note also P ⊆ NP ∩ co-NP: a fast solver serves as its own verifier for both YES and NO answers.

NP = YES answers have a short certificate that a polynomial-time verifier accepts. co-NP = NO answers have such certificates. P ⊆ NP, P ⊆ co-NP, and whether P = NP (or NP = co-NP) is open.

P ⊆ NP ⊆ … as code. A verifier takes (x, y). A polynomial decider becomes a verifier that ignores y (P ⊆ NP); P is closed under complement, so the complement also gets a verifier (P ⊆ co-NP); and a language is verified when some certificate makes the verifier accept (checking one is cheap, trying all is the exponential part):

Certificate checkers: Hamiltonian cycle, CLIQUE, subset sum, 3SAT

Each of the four languages below is in NP. For each we show the verifier at work on a good certificate, on a bad one, and on a certificate you type (format is stated in the input label; vertices are numbered from 0, edges are written a-b, parts are separated by |). A verifier must reject every bad certificate and accept a good certificate whenever the answer is YES.

Hamiltonian cycle (Hamiltonian cycle)

A Hamiltonian cycle of an undirected graph is a simple cycle that visits every vertex exactly once. Certificate: the vertex sequence. Time O(n) checks (with a hash set or matrix for edge lookups).

Tiny example. Square 0–1–2–3–0 with the diagonal 0–2 (edges 0-1, 1-2, 2-3, 3-0, 0-2). Certificate ⟨0,1,2,3⟩: the pairs (0,1), (1,2), (2,3) and the wrap-around pair (3,0) are all edges and every vertex appears once, so accept. Certificate ⟨0,1,2,1⟩ has only real edges between neighbours, yet it repeats vertex 1 and misses vertex 3, so the verifier must reject it.

Input size → what's feasible. n ≤ 10⁵ vertices and |E| ≤ 5·10⁵ edges → one hash set of 5·10⁵ keys plus one pass over n entries (≈ 10⁷ steps); trying all n! vertex orders is hopeless beyond n ≈ 12.

Dart notes: vertices are numbered 0..n−1. An undirected edge {a, b} is stored as the string 'min-max' so one hash-set lookup answers "is there an edge?" in O(1). Correctness is tested in verify/c34.dart against a check of every permutation on random graphs.

Forgetting a check. Two frequent bugs: skipping the wrap-around pair (last vertex back to first), and checking only that neighbours are joined without checking that the list is a permutation of the vertices (see the ⟨0,1,2,1⟩ example above).

The verifier reads the n entries once and does one edge lookup per entry: O(n) with a hash set or adjacency matrix. The certificate has n numbers of about lg n bits each, so it is polynomially short — the two conditions that put Hamiltonian cycle in NP.

CLIQUE

A clique is a set of vertices that are pairwise adjacent. CLIQUE = {⟨G, k⟩ : G has a clique of size k}. Certificate: the vertex set V′. Time O(|V′|²) edge lookups.

The CLIQUE verifier in Dart (certificate = the vertex list; an n×n matrix answers "is there an edge?" in O(1)):

Input size → what's feasible. n ≤ 2000, |E| ≤ 2·10⁵, certificate ≤ n entries → the matrix is 4·10⁶ cells and the pair checks ≤ C(k,2) ≈ 2·10⁶ lookups → fast; checking is O(n² + |E| + k²) while finding a clique has no known polynomial algorithm.

Subset sum

Given positive integers S and a target t, is there a subset summing to exactly t? Certificate: the chosen positions. Time linear in the number of chosen elements (times the cost of adding binary numbers). The first example is a ten-number set with t = 298.

The subset sum verifier in Dart (positions, not values; a hash set rejects repeats):

Input size → what's feasible. up to 10⁶ numbers ≤ 10⁹ → one pass, the sum ≤ 10¹⁵ fits a 64-bit int; searching all 2^10⁶ subsets is impossible.

3SAT

A Boolean formula is in 3-CNF if it is an AND of clauses, each an OR of exactly three literals (a literal is a variable or its negation). Certificate: a truth assignment. Time linear in the formula. (Below, clauses may have 1–3 literals so you can experiment; the first example is a satisfiable three-clause formula.)

The 3SAT verifier in Dart (a[0] is x₁, so literal ±i reads a[i − 1]):

Input size → what's feasible. m ≤ 10⁶ clauses over n ≤ 10⁵ variables → ≤ 3·10⁶ literals read once → fast; trying all 2ⁿ assignments already fails at n = 60.

Verifier vs solver: every verifier above runs in polynomial time and looks at the certificate only. That places Hamiltonian cycle, CLIQUE, subset sum and 3SAT in NP. Whether they are also in P is exactly what nobody knows — and the next sections show why they all stand or fall together.

Reductions and NP-completeness

Suppose you have a machine that solves "unlock this padlock" and a friend hands you a different lock. If you can always convert the friend's lock into an equivalent padlock question quickly, then your machine solves the friend's problem too. A reduction is that quick conversion.

Tiny example of a reduction. "Does this list contain a duplicate?" (L₁) reduces to sorting (L₂): sort the list in O(n lg n), then scan neighbours for equal values. The conversion is fast, so a fast sorter gives a fast duplicate finder. NP-completeness reductions have exactly this shape, only between harder problems.

Language L₁ is polynomial-time reducible to L₂, written L₁ ≤_P L₂, if there is a polynomial-time computable function f such that x ∈ L₁ ⇔ f(x) ∈ L₂ for every x. Read it as "L₁ is no harder than L₂ (up to polynomial time)". Consequences :

If L₁ ≤_P L₂ and L₂ ∈ P then L₁ ∈ P. (Run f, then the fast algorithm for L₂.)
≤_P is transitive: chains of reductions compose.
L is NP-hard if L′ ≤_P L for every L′ ∈ NP; NP-complete (L ∈ NPC) if additionally L ∈ NP.
If any NP-complete problem is in P then P = NP. Equivalently, if P ≠ NP then no NP-complete problem is in P.

To prove a new problem L NP-complete you do not reduce every NP problem to it; you show (1) L ∈ NP (give a verifier), (2) some known NP-complete L′ ≤_P L (give the reduction and prove "YES ⇔ YES"), and rely on transitivity. The very first NP-complete problem, circuit satisfiability (Cook–Levin theorem: it is in NP and it is NP-hard, so it is NP-complete), needs the direct proof that every NP language reduces to it: the computation of the verifier on a certificate is unrolled into a Boolean circuit of polynomial size. The chain of reductions this lesson builds:

The diagram below draws that chain, and the sections after it animate exactly those arrows, including the 12-vertex "widget" that vertex cover → Hamiltonian cycle places on every edge.

NP-hard does not mean "in NP". The halting problem is NP-hard (every NP problem reduces to it) but is not even decidable, so it is certainly not in NP. Only NP-hard and in NP gives NP-complete. Also, ≤_P is one-way: L₁ ≤_P L₂ says nothing about L₂ ≤_P L₁.

Idea of the Cook–Levin proof (why circuit satisfiability is NP-hard). A real computer is a circuit of gates over time. Run the polynomial-time verifier A on an instance x and an unknown certificate y for at most p(n) steps: unrolling those steps gives a Boolean circuit of polynomial size whose inputs are the certificate bits y. Fix x inside the circuit; the circuit is satisfiable exactly when some certificate makes A accept, i.e. exactly when x is a YES instance. So every language in NP reduces to circuit satisfiability.

To add a new problem L to the NP-complete club you need (1) a polynomial verifier for L and (2) a polynomial-time reduction from an already-NP-complete problem to L. Transitivity does the rest.

Reductions as code. A reduction is a function f; the rule ("L₁ ≤_P L₂ and L₂ ∈ P ⇒ L₁ ∈ P") is one line of composition, the "⇔" condition can be tested on a finite list of instances, and transitivity is function composition. If one NP-complete language had a fast decider, every NP language would inherit it through its reduction:

The picture: P, NP, co-NP, NPC and the reduction chain

Think of a mountain range of difficulty. P is the foothills (problems we can climb). NP is the whole range that we can at least check a summit photo for. The NP-complete problems are the highest peaks that all look like each other: reach one and you can reach all. co-NP is the mirror-image range where the "NO" photos are checkable.

Venn diagram of what is believed (nobody has proved P ≠ NP or NP ≠ co-NP). The drawn regions are facts only where stated: P ⊆ NP ∩ co-NP is a theorem; NP-complete problems lie in NP; if any NP-complete problem were also in co-NP then NP = co-NP.

If P = NP the whole picture collapses to one region (every problem in P except the trivial ones would be NP-complete). Until then, the NP-complete blob is the thing to fear: one polynomial algorithm for it would pull the entire NP oval into P.

The chain of reductions that populates the NP-complete blob. Each arrow is a polynomial-time reduction from the problem at its tail to the problem at its head, and each is animated in the matching section below. Every language in NP reduces to circuit satisfiability (Cook–Levin), so the whole tree is NP-hard; each box is also in NP (verifiers in the certificate-checkers section).

Read every arrow as "≤_P": A → B means A is no harder than B. Hardness therefore flows along the arrows, from circuit satisfiability to TSP.

circuit satisfiability → SAT

A circuit is a wiring diagram of AND, OR and NOT gates; circuit satisfiability asks if some input setting lights the output bulb. A formula is the same wiring written as algebra. The translation labels every wire with a name and writes one "this wire equals what its gate computes" sentence per gate, then says "and the output wire must be on".

Input format: n | gate; gate; … where n is the number of input wires (wires 1..n), and each gate is AND a b [c], OR a b [c] or NOT a reading earlier wires. Gate number g outputs wire n+g. The last gate is the output. The first example is a 3-input circuit with 3 gates, output wire 6.

Tiny example. Two inputs x₁, x₂. Gate 1 = NOT x₂ (wire 3), gate 2 = x₁ AND wire 3 (wire 4, the output). The formula is x₄ ∧ (x₃ ↔ ¬x₂) ∧ (x₄ ↔ (x₁ ∧ x₃)). The only satisfying input is x₁ = 1, x₂ = 0: then wire 3 = 1 and wire 4 = 1. The formula and the circuit agree on which inputs light the bulb.

The formula class used by the reductions (a small tree; eval is the meaning of a formula under an assignment, with 1-based variables (so −i can mean ¬x_i) read as a[v − 1]):

What circuit satisfiability asks, in code: evaluate every wire, and try all 2ⁿ inputs for the brute-force reference:

The claims about this reduction as code: the formula has linear size and its satisfying assignments match the circuit's satisfying inputs one to one:

Why one variable per wire (the pitfall above) in numbers: a chain of gates where every wire feeds two gates doubles the naive formula at every level, while the wire-variable formula grows by 5 symbols per gate:

The Cook–Levin idea in code. Unrolling a polynomial-time verifier into a circuit: the subset sum verifier "the chosen numbers add up to t" becomes a circuit with ripple-carry adders whose inputs are the certificate bits. The circuit is satisfiable exactly when the instance is a YES instance, and it has only O(n · bits) gates:

Input size → what's feasible. a circuit with up to 10⁶ gates gives a formula of about 5·10⁶ symbols (linear); brute-forcing circuit satisfiability itself costs 2ⁿ inputs, so n ≤ 20 inputs is the exact-solver limit (10⁶ × gates).

Dart notes: wires are numbered from 1; in the code a wire is i (1-based) and the list element is w[i − 1], which is the only index shift. The circuit's output is the last gate, wire n + gs.length. Fm is the small formula-tree class at the top of verify/c34.dart.

Forgetting the output clause. The formula must also contain the single variable x_out ("the output wire is 1"). Without it every input has a consistent set of wire values, so the formula would be satisfiable even for a circuit that can never light the bulb.

Why one variable per wire? If a gate's output feeds two later gates, writing the formula as a nested expression copies the sub-formula twice; repeated fan-out can double the size at every level and give exponential size. Naming each wire and adding one small "wire = gate(inputs)" equivalence per gate keeps the formula linear in the circuit. Every satisfying assignment of the formula corresponds one-to-one to a satisfying input of the circuit, because the gate equivalences force every wire value.

Circuit satisfiability ≤_P SAT: n + #gates variables, one ↔ per gate, plus the output variable. Linear size, YES ⇔ YES.

SAT → 3SAT

A tangled sentence is hard to check mechanically. Break it into tiny sentences with at most three names each ("y₂ means x₁ → x₂"), and turn each tiny sentence into a checklist of "forbidden combinations". Finally pad every checklist line to exactly three items. The pieces together say the same thing as the original sentence.

Input: a Boolean formula written with x1..x4 (at most 8 connectives), ~ (not), &, |, ->, <-> and parentheses. The first example is ((x₁ ∧ x₂) → ¬x₃) ∨ (x₄ ↔ x₁), which has 5 connectives.

Tiny example. φ = (x₁ → x₂) has one internal node y₁ ↔ (x₁ → x₂). Of the 8 rows of its truth table, 4 disagree with the equivalence (for instance y₁ = 1 while x₁ = 1, x₂ = 0), so they become 4 clauses of 3 literals. The root must be true: the clause (y₁) is padded into 4 clauses using two new variables p and q. Total: 8 clauses, and the 3-CNF has a satisfying assignment exactly when x₁ → x₂ does.

The size and equivalence claims as code (at most 4 clauses of exactly 3 literals per parse-tree node plus the 4 root clauses; φ satisfiable ⇔ φ′ satisfiable):

Input size → what's feasible. a formula with 10⁵ connectives gives at most 4·10⁵ + 4 clauses (linear); the exhaustive equivalence test in the code is only for ≤ 4 original variables plus the new ones (≤ 14 in all).

Dart notes: variables are numbered from 1 so that a negative int can mean a negation; satTo3Cnf hands out the next unused number for each internal node's variable y, then for the padding variables p and q, and returns the clause list together with the new variable count. Nothing is shifted by 1 except the list lookups a[lit − 1] in evaluation code.

Two slips. (1) Leaving a clause with 1 or 2 literals: 3-CNF needs exactly three, so pad with p and ¬p (and q, ¬q) in every sign combination; the four copies are equivalent to the short clause whatever p and q are. (2) Forgetting the root clause (y₁): without it the tree's equivalences are satisfiable even when φ is false.

A CNF clause is violated by exactly one assignment (the one that makes all its literals false). So listing every row of the small truth table where "y ≠ operation(children)" as one clause forbids exactly those rows and nothing else; that is why the conversion is correct and why the size is linear: each parse-tree node contributes at most 4 clauses of size 3.

SAT ≤_P 3SAT: parse tree → variable per internal node → truth-table rows that violate the node become clauses → pad to three literals → add the root clause. Linear size, φ satisfiable ⇔ φ′ satisfiable.

3SAT → CLIQUE

A committee has to seat one representative from each of k clubs, and two representatives may sit together only if they do not contradict each other. A seating of all k with everybody compatible is a k-clique; a satisfying assignment is a way to pick one true literal from every clause with no contradictions.

Input: clauses separated by ;, literals separated by spaces (3 = x₃, -3 = ¬x₃); up to 5 clauses, 3 literals each, variables x₁..x₄. The first example is C₁ = ¬x₁ ∨ x₂ ∨ x₃, C₂ = x₁ ∨ ¬x₂ ∨ x₃, C₃ = x₁ ∨ x₂ ∨ ¬x₃.

Tiny example. φ = (x₁ ∨ x₂) ∧ (¬x₁ ∨ x₂). Vertices: 0 = x₁ and 1 = x₂ (clause 1), 2 = ¬x₁ and 3 = x₂ (clause 2). Edges join vertices of different clauses unless they contradict: {0,3} (x₁, x₂), {1,2} (x₂, ¬x₁), {1,3} (x₂, x₂); the pair {0,2} (x₁, ¬x₁) is skipped. k = 2, and the 2-clique {1,3} says "make x₂ true in both clauses", which satisfies φ.

Both directions of "satisfiable ⇔ k-clique" as code, and the size bound (3m vertices, at most C(3m, 2) edges):

Input size → what's feasible. m = 500 clauses → 1500 vertices and up to 1.1·10⁶ edges (a double loop, fine); m = 10⁵ would make 4.5·10¹⁰ edges — still polynomial, but too big to build.

Dart notes: vc[i] is the clause of vertex i and vl[i] its literal (a negative int is a negation), so "contradictory" is the test vl[a] == -vl[b]. Vertices are numbered 0.. in reading order.

Two slips. (1) Adding edges inside a clause: then a k-clique could pick two literals of one clause and none from another, which breaks "one true literal per clause". (2) Thinking the clique must fix every variable: variables not chosen by the clique may take any value.

The graph has one vertex per literal occurrence, so 3m vertices for m clauses, and at most C(3m, 2) edges: quadratic size, built by one double loop. Direction ⇒: choose a true literal from each clause; those m literals never contradict, so their vertices are pairwise adjacent. Direction ⇐: the m vertices of a m-clique sit in different clauses (no edges inside a clause), and setting each of their literals true is consistent (no contradiction edges) and satisfies every clause.

3SAT ≤_P CLIQUE: a vertex per literal occurrence, an edge between different clauses unless the literals are complementary, k = number of clauses.

CLIQUE → vertex cover

A party with friendships (edges). A clique is a group where everyone knows everyone. Flip the picture to "who does not know whom" (the complement graph). Send home everybody outside the clique: every non-friendship pair now has at least one person sent home, because two members of the clique are friends and so never form a non-friendship pair. The people sent home are a vertex cover of the non-friendship graph.

A vertex cover of G is a set of vertices touching every edge. Input: n | edges | k. The first example has 7 vertices: a triangle {0,1,2}, a tail 2-3-4-5-6 and one extra edge 3-5.

Tiny example. G has edges 0-1, 0-2, 1-2, 0-3 (a triangle {0,1,2} with a pendant vertex 3). The triangle is a clique of size 3, so k = 3, n = 4. The complement has edges 1-3 and 2-3 (the pairs missing from G). The set V − clique = {3} touches both, so it is a vertex cover of size n − k = 1.

The claim "S is a clique of G ⇔ V − S is a vertex cover of the complement" (and the independent-set version) as code, tested on every subset S:

Transitivity as code: the two reductions composed into one function 3SAT → vertex cover, with the instance sizes it produces:

Input size → what's feasible. n ≤ 2000 → the complement has up to 2·10⁶ edges (n² table, 4·10⁶ steps); the brute-force cover used for testing is exponential and only for n ≤ 20.

Dart notes: vertices are 0..n−1 in both the picture and the code. The whole reduction is complementGraph plus the new bound n − k; nothing else changes.

Wrong bound. The cover size is n − k, not k, and it lives in the complement graph, not in G itself. In G the same vertices V − clique are not a cover of anything in general.

The same argument shows independent set ↔ vertex cover: S is an independent set (no edges inside) exactly when V − S is a vertex cover, so a graph has an independent set of size k iff it has a vertex cover of size n − k. And "independent set in G" is "clique in the complement of G". Together they make CLIQUE, independent set and vertex cover three faces of one problem.

vertex cover → Hamiltonian cycle (widgets and selectors)

A city inspects every road with k night guards. Each road is a short two-lane tunnel (the widget). Each guard picks one intersection (a vertex) and walks through every tunnel that starts there in one long chain. If a road is watched from just one end, that guard must inspect the whole tunnel; if both ends are watched, each guard inspects only his own lane. A guard route that inspects all the tunnels exists exactly when the k chosen intersections touch every road, that is, when they are a vertex cover.

Given G and k, build an undirected graph G′ that has a Hamiltonian cycle iff G has a vertex cover of size k. Three ingredients, all animated below:

Widgets. Every edge {u, v} of G becomes a copy of the widget: 12 vertices [u,v,1..6] and [v,u,1..6] and 14 edges. Only the four terminals [u,v,1], [u,v,6], [v,u,1], [v,u,6] get edges to the outside. The widget forces the cycle to go through it in one of three ways: all 12 vertices from [u,v,1] to [u,v,6] both columns as two separate 6-vertex paths or all 12 from [v,u,1] to [v,u,6] — the first player below checks this by exhaustive search.
Chains. For every vertex u, string together the widgets of the edges at u: join [u,e,6] of one widget to [u,e′,1] of the next. A path along the chain "covers" all edges at u.
Selectors. Add k selector vertices s₁..s_k, each joined to the first and to the last vertex of every chain. Only k chains fit between the selectors, so the cycle can pick at most k vertices; every edge's widget must still be visited, which forces the k picked vertices to cover all edges.

Size: |V′| = 12|E| + k and |E′| = 16|E| + (2k − 1)|V| (this assumes every vertex lies on an edge, as the input format below does). Input format: n | edges | k with 2 ≤ n ≤ 5, 1 ≤ edges ≤ 5 and 1 ≤ k ≤ n, for example 4|0-1,1-2,2-3|2.

Tiny example. G is the single edge {0,1} with k = 1. G′ has 12 + 1 = 13 vertices and 14 + 4 = 18 edges. The cover {0} gives the cycle s₁ → [0,1,1] → (all 12 widget vertices) → [0,1,6] → s₁, which visits all 13 vertices exactly once.

The widget claim as code: all 2¹⁴ subsets of the widget's 14 edges are tried; only three terminal pairings can occur inside a Hamiltonian cycle, and the crossing never does:

The size formula of this reduction and the "cover of size ≤ k ⇔ Hamiltonian cycle" claim as code:

Input size → what's feasible. |E| ≤ 10⁴, n ≤ 500 → G′ has up to 1.2·10⁵ vertices and 6.6·10⁵ edges and building it costs n·|E| = 5·10⁶ steps; searching G′ for a Hamiltonian cycle is exponential in general (the pruned search handles the ≤ 77-vertex graphs of this lesson).

Dart notes: the widget vertex [u,v,i] (i = 1..6) becomes the integer 12·t + (u == edges[t][0] ? 0 : 6) + (i − 1), where t is the index of the edge {u,v}: position i shifts down by one to 0..5, and the second column of the widget is offset by 6. Selectors get the ids 12m .. 12m + k − 1. The generated graph is tested for the counts 12|E| + k and 16|E| + (2k − 1)|V| and for "cover of size ≤ k ⇔ Hamiltonian cycle" on over a hundred random graphs, using an independent backtracking search (hamCycleSearch).

Three easy mistakes. (1) The Hamiltonian cycle of G′ is not a cycle of G; the cover is read off from which chains the selectors lead into. (2) A cover of size smaller than k is fine: pad it with any extra vertices, because a superset of a cover is still a cover (the walkthrough does exactly this). (3) A vertex with no edge has no widget and no chain, which is why the input format rejects isolated vertices; delete them first, they never matter for covering.

Why "Hamiltonian cycle ⇒ cover" also holds. Remove the k selectors from a Hamiltonian cycle: k paths remain, each starting at the first vertex of some chain and ending at the last vertex of a chain (only those vertices touch selectors). Because of the widget rule (enter through the top of a column, leave through the bottom of the same column), each path stays on one chain and visits the widgets of that vertex only. Every widget is visited, so every edge {u,v} has u or v among the k chains used, and those ≤ k vertices form a vertex cover. Both directions together make YES ⇔ YES; the last frames of every walkthrough confirm it against an independent brute-force search of G′.

Vertex cover ≤_P Hamiltonian cycle: widget per edge, chain per vertex, k selectors. |V′| = 12|E| + k, |E′| = 16|E| + (2k − 1)|V|. A cover of size k ⇔ a Hamiltonian cycle in which selector j leads into the chain of the j-th cover vertex.

Hamiltonian cycle → TSP

A delivery driver may only use existing roads for free but is allowed to drive on "invisible" roads at a fine of 1 each. If a route through every town costs nothing, it never used an invisible road, so it was a route along real roads only.

The traveling-salesman problem TSP asks, for a complete graph with integer costs c(u,v) and a bound k: is there a Hamiltonian cycle (a tour) of total cost ≤ k? It is in NP (certificate: the tour). Reduction from Hamiltonian cycle: complete the graph, c = 0 on edges of G and 1 otherwise, k = 0. (The previous section showed Hamiltonian cycle NP-hard by reduction from vertex cover, so this arrow finishes the chain.) Input: n | edges with 3 ≤ n ≤ 7.

Tiny example. G = the path 0–1–2 (edges 0-1, 1-2), n = 3. Complete it: c(0,1) = 0, c(1,2) = 0, c(0,2) = 1. The only tour is 0 → 1 → 2 → 0 with cost 0 + 0 + 1 = 1 > 0, so the answer is NO — correct, since a path has no Hamiltonian cycle.

The reduction checked on EVERY graph with 3, 4 and 5 vertices (8 + 64 + 1024 graphs): G has a Hamiltonian cycle ⇔ the TSP instance has a tour of cost ≤ 0:

Input size → what's feasible. n ≤ 2000 → the cost matrix has 4·10⁶ entries; solving the TSP instance exactly: n ≤ 10 by brute force (9! = 362,880 tours), n ≤ 16 with Held–Karp (2¹⁶·16² ≈ 1.7·10⁷ steps), n = 25 would need 2²⁵·625 ≈ 2·10¹⁰ steps and 2²⁵·25 ≈ 8·10⁸ table cells.

Dart notes: vertices 0..n−1; the matrix is symmetric and the diagonal is 0 because a tour never uses it. The exact solvers tspBrute and heldKarp (with its bitmask index explained below) are in verify/c34.dart and cross-checked on random matrices.

The bound is 0, not "small". The reduction asks for a tour of cost at most k = 0, and costs must be integers 0 and 1. A tour of cost 1 has used one non-edge, so it is not a Hamiltonian cycle of G.

Exact TSP is exponential, but not as bad as n!. Brute force tries (n−1)! tours. The Held-Karp dynamic program stores, for each set S of visited cities and each last city j ∈ S, the cheapest path from city 0 covering exactly S ending at j; it runs in O(2ⁿ n²) time and O(2ⁿ n) space — the animation above uses it. Both algorithms and the reduction are tested in verify/c34.dart. In the bitmask mask, bit i means "city i already visited" (cities are 0..n−1; city 0 is the fixed start). See dynamic programming for the general "table of subproblems" idea.

Hamiltonian cycle ≤_P TSP: complete the graph, real edges cost 0, missing edges cost 1, k = 0. A tour of cost 0 is a Hamiltonian cycle.

3SAT → subset sum (and pseudo-polynomial time)

A vending machine only accepts exact change. Each variable is a choice between two coins ("true coin" or "false coin"); each clause is a counter that must reach exactly 4 tokens, where clause-satisfying literals hand out tokens and two spare coins can top up the rest. Because every column of the sum stays under 10, the columns never spill into each other, like separate meters.

Input: clauses like the previous section (up to 4 clauses, variables x₁..x₄, no variable twice in one clause). The first example is C₁ = x₁ ∨ ¬x₂ ∨ x₃, C₂ = ¬x₁ ∨ x₂ ∨ ¬x₃, C₃ = x₂ ∨ x₃, giving the set {100100, 100010, 10011, 10100, 1101, 1010, 100, 200, 10, 20, 1, 2} and target 111444.

Tiny example. One variable, one clause: φ = (x₁), so n = 1, k = 1, two digits. Numbers: v₁ = 11 (x₁ true: digit 1 in the variable column and 1 in the clause column), v′₁ = 10 (x₁ false), slack s₁ = 1 and s′₁ = 2. Target = 14. The subset {11, 1, 2} sums to 14 (x₁ = true). With v′₁ = 10 the best possible total is 10 + 1 + 2 = 13 < 14, so x₁ = false correctly fails.

The "no carries" argument as code: the largest possible column sum, and the column sums of any subset compared with the target's digits:

Input size → what's feasible. n + k ≤ 15 digits in this lesson (≤ 19 still fits a 64-bit int); the subset-sum table of the first section would need about 10^n+k cells for the reduction's target t, so the size of t, not the number of numbers, is what makes subset sum hard.

Dart notes: place(col) is the power of ten of column col (column 0 is the leftmost digit); variables are 1..n, the code loops i = 1..n and writes to column i − 1, which is the index shift. Clause j uses column n + j. Numbers are held in 64-bit ints, so n + k ≤ 18 is the safe limit for the Dart version.

Why this does not contradict the DP. subset sum can be solved in O(n·t) time by a table dp[s] ("can I make sum s?"), which looks polynomial. It is only pseudo-polynomial: t is written in binary, so t itself is exponential in the input length. The numbers produced by this reduction have n + k digits, so t is about 10^n+k — the table would be exponentially large. A DP that is polynomial in the value of the numbers is not a polynomial-time algorithm in the size of the input.

Why the base-10 digits never carry. A variable column has exactly two non-zero digits (v_i and v′_i, each 1), so it sums to at most 2. A clause column receives at most three 1s from literals plus at most 1 + 2 from the slack numbers: at most 6, less than 10. With no carries, the sum of a subset equals the target exactly when every column matches separately, which is exactly the statement "each variable picked once, each clause satisfied with total 4 after slack".

3SAT ≤_P subset sum: 2n + 2k numbers of n + k digits, target 1…1 4…4. Subset-sum has a table algorithm O(n·t) that is only pseudo-polynomial, because t is exponential in its digit count.

How big does the whole chain get?

Each reduction is a photocopier that enlarges the page by a fixed power: 3× then 2× then 12× is still a manageable stack of paper, while a copier that doubled the page once per line of text would run out of paper. Polynomial-time reductions enlarge the instance polynomially, and chaining polynomial enlargements stays polynomial.

This is the running-time argument for the whole lesson: one formula is pushed through 3SAT → CLIQUE → vertex cover → Hamiltonian cycle → TSP and the size of each produced instance is counted (the graph for vertex cover → Hamiltonian cycle is built for real, the count is the actual number of vertices and edges). Input: clauses like the earlier sections, up to 5 clauses of at most 3 literals, variables x₁..x₄.

Tiny example. φ = (x₁) ∧ (¬x₁): 2 literal occurrences, the CLIQUE graph has 2 vertices and no edge (the two literals contradict), its complement has 1 edge, so G′ is one widget: 12 vertices and 14 edges, and TSP gets 12 cities, 66 distances.

"Big" is not "exponential". A reduction may produce an enormous instance and still be perfectly legitimate. What matters is that the size is bounded by a polynomial in the input size. A reduction that builds a truth table with 2ⁿ rows is not polynomial, however clever.

Symbolically for m clauses (≈ 3m literal vertices L): CLIQUE graph Θ(L²) edges; complement Θ(L²); Hamiltonian cycle graph 12·Θ(L²) + (2k′−1)·L = O(L²) edges and vertices with k′ = L − m; TSP N² with N = O(L²), so O(L⁴) = O(m⁴) distances. Each factor is a polynomial, and by transitivity the composed reduction 3SAT ≤_P TSP is polynomial too.

Size of a chain of reductions = product of the individual polynomial blow-ups = still polynomial. That is what lets NP-hardness travel along the arrows of the chain.

Chain sizes as code. For m clauses (L = 3m literal vertices) the worst-case instance sizes along the whole chain, and the check that the number of TSP distances grows like m⁴:

Input size → what's feasible. m = 3 clauses → L = 9, ≤ 36 edges, ≤ 438 cities (≈ 9.6·10⁴ distances); m = 30 → L = 90, ≤ 4005 edges, ≤ 48,120 cities (≈ 1.2·10⁹ distances): polynomial, yet already too large to build, which is why the page only counts.

How an NP-completeness proof is written

Template for showing that a language L is NP-complete:

L ∈ NP. Describe a certificate and a polynomial-time verifier (as in the certificate-checkers section).
Pick a known NP-complete L′ that looks similar (CLIQUE for graph "choose a group" problems, 3SAT for logic-like problems, subset sum for number problems, Hamiltonian cycle for tour problems).
Give a function f mapping every instance x of L′ to an instance f(x) of L, computable in polynomial time.
Prove x ∈ L′ ⇔ f(x) ∈ L. Two directions: a YES certificate for x becomes a YES certificate for f(x), and a YES certificate for f(x) can be turned back into one for x. (The animations above check exactly this on small instances.)
Conclude: L′ ≤_P L, L′ is NP-hard, so L is NP-hard by transitivity; together with step 1, L ∈ NPC.

The most common mistake: reducing in the wrong direction. To show L is hard you reduce from a known-hard problem to L (known-hard ≤_P L). Reducing L to a known-hard problem only shows L is no harder than it — which proves nothing.

Big picture, assuming P ≠ NP: P is a proper subset of NP, and NP-complete problems live in NP − P. Ladner's theorem says that (if P ≠ NP) NP also contains problems that are neither in P nor NP-complete. Factoring and graph isomorphism are the classic suspects for that middle ground. If someone finds a polynomial algorithm for any single NP-complete problem, every problem in NP collapses into P at once.

Quiz

Interview questions

Cheat sheet

Topic	Key fact	Cost	Remember
P	decidable in polynomial time	O(n^c)	closed under composition, complement
NP	YES answers have short certificates	verify in polynomial time	P ⊆ NP; P = NP is open
co-NP	complements of NP languages	NO answers have short certificates	P ⊆ NP ∩ co-NP; NP = co-NP is open
Hamiltonian cycle verifier	permutation + n edge checks	O(n)	certificate = vertex order
CLIQUE verifier	all pairs adjacent	O(k²)	certificate = vertex set
Subset sum verifier	distinct positions, sum = t	O(\|S′\|) additions	positions, not values
3SAT verifier	each clause has a true literal	O(formula)	certificate = assignment
Circuit satisfiability → SAT	one variable per wire, one ↔ per gate	linear size	never expand shared sub-circuits
SAT → 3SAT	y-variable per node, truth-table → clauses, pad with p, q	linear size	root clause (y₁) must be included
3SAT → CLIQUE	vertex per literal occurrence, edges across clauses unless contradictory, k = #clauses	O(m²)	k-clique = one true literal per clause
CLIQUE → vertex cover	complement graph, k′ = n − k	O(n²)	V − clique = cover
P / NP / co-NP / NPC	P ⊆ NP ∩ co-NP; NPC ⊆ NP; NPC ∩ P = ∅ unless P = NP	—	Venn picture is believed, not proved
Vertex cover → Hamiltonian cycle	12-vertex widget per edge, chain per vertex, k selectors	\|V′\| = 12\|E\| + k, \|E′\| = 16\|E\| + (2k − 1)\|V\|	cover of size k ⇔ Hamiltonian cycle
Hamiltonian cycle → TSP	complete graph, cost 0 / 1, k = 0	O(n²)	cost-0 tour = Hamiltonian cycle
3SAT → subset sum	2n + 2k base-10 numbers of n + k digits, target 1…14…4	O((n+k)²)	no carries: column sum ≤ 6
Whole chain 3SAT → TSP	each step polynomial, so the composition is	≈ O(m⁴) TSP distances	big is fine, exponential is not
Subset-sum DP	dp[s] over sums 0..t	O(n·t) time, O(t) space	pseudo-polynomial only
TSP exact	brute force vs Held-Karp	O(n!) vs O(2ⁿn²)	Held-Karp uses bitmask over visited cities