47.02.03 · theoretical-cs / complexity-fundamentals

Classic NP-Complete Problems: SAT, 3SAT, Clique, Vertex Cover, and Hamiltonian Cycle

shipped3 tiersLean: nonepending prereqs

Anchor (Master): Sipser 2013 Introduction to the Theory of Computation 3e (Cengage) §7.4-7.5; Cormen, Leiserson, Rivest & Stein 2022 Introduction to Algorithms 4e (MIT Press) §34.3-34.5; Garey & Johnson 1979 Computers and Intractability (Freeman) §2-3 (catalogue of NP-complete problems, reduction strategies, strong NP-completeness)

Intuition Beginner

Some problems have a convenient property: once you find a solution, checking it is easy. A jigsaw puzzle is hard to solve, but verifying that a completed puzzle is correct takes a glance. A Sudoku is hard to fill in, but checking a filled grid is quick.

NP-complete problems are the hardest problems in NP — the hardest problems where solutions can be checked quickly. If you could solve any one of them quickly, you could solve all of them quickly, because they are all secretly the same problem in disguise.

The disguises are called reductions. A reduction from problem A to problem B is a fast translation: it converts any instance of A into an instance of B such that the answer is preserved. If you can solve B, the reduction lets you solve A by translation. When A reduces to B and B is in NP, then B is at least as hard as A.

SAT asks: given a Boolean formula, is there a way to set its variables to true and false that makes the whole formula true? Cook and Levin proved that SAT is NP-complete: every problem in NP reduces to SAT. This was the first known NP-complete problem.

From SAT, a chain of reductions connects dozens of seemingly unrelated problems. 3SAT (a restricted form of SAT) reduces to CLIQUE (does a graph have a group of mutually connected vertices of a given size?), which reduces to VERTEX-COVER (can you delete a small set of vertices to eliminate all edges?), and so on. Each reduction opens a new window into the same underlying hardness.

Visual Beginner

The reduction chain connecting NP-complete problems:

Any NP problem
       |
       ↓  (Cook-Levin)
      SAT
       |
       ↓  (clause splitting)
     3SAT
      / \
     ↓   ↓
  CLIQUE  HAM-CYCLE
     |
     ↓  (complement graph)
  VERTEX-COVER
     |
     ↓
  SUBSET-SUM

Problem	Input	Question
SAT	Boolean formula	Is it satisfiable?
3SAT	Formula with 3-literal clauses	Is it satisfiable?
CLIQUE	Graph $G$ , integer $k$	Does $G$ have a $k$ -clique?
VERTEX-COVER	Graph $G$ , integer $k$	Does $G$ have a $k$ -vertex cover?
HAM-CYCLE	Graph $G$	Does $G$ have a Hamiltonian cycle?

Worked example Beginner

We reduce 3SAT to CLIQUE.

Given a 3SAT formula $ϕ = (l_{1, 1} \lor l_{1, 2} \lor l_{1, 3}) \land \dots \land (l_{k, 1} \lor l_{k, 2} \lor l_{k, 3})$ with $k$ clauses, build a graph $G$ as follows. Create three vertices per clause, labelled $v_{i, 1}, v_{i, 2}, v_{i, 3}$ for clause $i$ . Connect two vertices $v_{i, a}$ and $v_{j, b}$ (with $i \neq = j$ ) if their corresponding literals are compatible: the literal $l_{i, a}$ is not the negation of $l_{j, b}$ .

Claim: $ϕ$ is satisfiable iff $G$ has a clique of size $k$ .

If $ϕ$ is satisfiable, each clause has at least one true literal. Pick one true literal per clause. The corresponding vertices form a clique: any two of them are from different clauses, and their literals are both true under the satisfying assignment, so they cannot be negations of each other.

If $G$ has a clique of size $k$ , then the clique contains one vertex per clause (since there are no edges within a clause group). Set each literal in the clique to true. Since clique vertices are compatible, no literal contradicts another. Assign remaining variables arbitrarily. This satisfies $ϕ$ .

Example: $ϕ = (x \lor y \lor \neg z) \land (\neg x \lor z \lor y)$ . The graph has 6 vertices. Vertex $(1, x)$ connects to $(2, z)$ and $(2, y)$ but not to $(2, \neg x)$ (conflict). Vertex $(1, y)$ connects to $(2, \neg x)$ , $(2, z)$ , and $(2, y)$ . Setting $x = true, y = true, z = true$ satisfies $ϕ$ . The corresponding clique picks $(1, x)$ and $(2, z)$ (or other valid pairs).

Check your understanding Beginner

Formal definition Intermediate+

Definition (NP-completeness). A language $L$ is NP-complete if:

$L \in NP$ .
For every $L^{'} \in NP$ , $L^{'} \leq_{p} L$ (every NP problem polynomial-time reduces to $L$ ).

Theorem (Cook-Levin). SAT is NP-complete.

The proof constructs, for any NP machine $M$ and input $w$ , a Boolean formula $ϕ_{M, w}$ of size polynomial in $∣ w ∣$ such that $ϕ_{M, w}$ is satisfiable iff $M$ accepts $w$ . The formula encodes the entire computation tableau: rows are time steps, columns are tape cells, and variables $x_{i, j, s}$ indicate that cell $j$ at time $i$ contains symbol $s$ . Clauses enforce: (a) a valid start configuration, (b) each cell has exactly one symbol, (c) each window of three consecutive cells transitions correctly according to $M$ 's transition function, and (d) some cell contains an accept state ^{[Sipser §7.4]}.

Reduction 1: SAT to 3SAT. Given a SAT instance $ϕ$ , convert each clause $C = (l_{1} \lor l_{2} \lor \dots \lor l_{k})$ with $k > 3$ into a chain of 3-literal clauses using fresh variables $y_{1}, \dots, y_{k - 3}$ :

$(l_{1} \lor l_{2} \lor y_{1}) \land (\neg y_{1} \lor l_{3} \lor y_{2}) \land \dots \land (\neg y_{k - 3} \lor l_{k - 1} \lor l_{k})$ .

This gadget is satisfiable iff the original clause is. The reduction produces a 3CNF formula of size $O (∣ ϕ ∣)$ .

Reduction 2: 3SAT to CLIQUE. Given a 3CNF formula with $k$ clauses, construct the graph described in the worked example. The graph has $3 k$ vertices and at most $9 k^{2}$ edges. $G$ has a $k$ -clique iff $ϕ$ is satisfiable.

Reduction 3: CLIQUE to VERTEX-COVER. $G$ has a clique of size $k$ iff $\overline{G}$ (the complement graph) has a vertex cover of size $∣ V ∣ - k$ . The complement is computable in polynomial time.

Counterexamples to common slips

"NP means 'not polynomial.'" NP stands for Nondeterministic Polynomial time. It is the class of problems solvable in polynomial time on a nondeterministic machine. Many NP problems have no known polynomial-time algorithm, but NP does not mean "hard."
"NP-complete means 'the hardest problem there is.'" NP-complete means the hardest problem in NP. There are much harder problems outside NP (e.g., the halting problem, which is undecidable).
"A reduction from A to B means A and B are equally hard." A reduction $A \leq_{p} B$ means B is at least as hard as A. B could be harder. NP-completeness of B means B is at least as hard as every NP problem.

Key theorem with proof Intermediate+

Theorem (3SAT to HAM-CYCLE reduction). 3SAT $\leq_{p}$ HAM-CYCLE.

Proof sketch. Given a 3CNF formula $ϕ$ with $n$ variables and $k$ clauses, construct a graph $G$ with a Hamiltonian cycle iff $ϕ$ is satisfiable. The construction uses two types of gadgets.

Variable gadget. For each variable $x_{i}$ , create a diamond-shaped subgraph of 12 vertices arranged so that a Hamiltonian cycle traversing this subgraph must go either left-to-right (encoding $x_{i} = true$ ) or right-to-left (encoding $x_{i} = false$ ).

Clause gadget. For each clause $C_{j}$ , create a single node. This node can be visited by the Hamiltonian cycle only by "detouring" through the variable gadget corresponding to a literal in $C_{j}$ that is set to true. If $x_{i}$ appears positively in $C_{j}$ , the detour uses the rightward path through the $x_{i}$ gadget; if $\neg x_{i}$ appears, it uses the leftward path.

The graph has $O (n + k)$ vertices and edges, and the construction is polynomial. A Hamiltonian cycle in $G$ corresponds to a consistent truth assignment that satisfies every clause, and vice versa. $□$

Bridge. The chain of reductions from SAT through 3SAT, CLIQUE, VERTEX-COVER, and HAM-CYCLE builds toward the entire theory of NP-completeness as a unified phenomenon: all NP-complete problems are polynomial-time equivalent, and this is exactly the foundational reason that resolving P vs NP for any one of them resolves it for all. The reductions appear again in 47.02.04 where the polynomial hierarchy layers additional quantifier alternations on top of NP, and in 47.04.04 where bipartite matching provides a contrasting example of a graph problem that sits firmly in P. The central insight is that the reduction is a constructive encoding of one problem's structure into another's, and this is exactly what makes NP-completeness a robust and transferable notion. Putting these together with the Cook-Levin theorem shows that SAT is the universal NP problem: every NP computation can be encoded as a Boolean formula, and from there, translated into the language of graphs, numbers, or any other NP-complete domain.

Exercises Intermediate+

Exercise 6 (hard, symbolic).

Prove that SUBSET-SUM is NP-complete by reducing 3SAT to it. SUBSET-SUM asks: given a set $S$ of integers and a target $t$ , is there a subset $S^{'} \subseteq S$ with $\sum_{s \in S^{'}} s = t$ ?

Hint

Use a base-10 (or higher) encoding where each digit position corresponds to a variable or a clause. Create two numbers per variable (one for true, one for false) and two slack numbers per clause.

Answer

Given a 3CNF formula with $n$ variables and $k$ clauses, represent numbers in base $B = k + 1$ (to prevent carries between digit positions). Each number has $n + k$ digits: the first $n$ digits correspond to variables, the last $k$ to clauses.

For each variable $x_{i}$ : create number $v_{i}$ with digit 1 in position $i$ (variable position) and digit 1 in each clause position $j$ where $x_{i}$ appears positively; and number $v_{i}^{'}$ with digit 1 in position $i$ and digit 1 in each clause position $j$ where $\neg x_{i}$ appears.

For each clause $C_{j}$ : create two slack numbers $s_{j}, s_{j}^{'}$ with digit 0 everywhere except position $n + j$ , where they have digits 1 and 2 respectively.

Target $t$ has digit 1 in each variable position and digit 3 in each clause position.

The subset picks exactly one of ${v_{i}, v_{i}^{'}}$ per variable (contributing 1 to position $i$ ) and some slacks to bring each clause position up to 3. The clause position gets 1 from each satisfied literal plus slacks to reach 3. A satisfying assignment maps to a subset summing to $t$ , and vice versa.

Exercise 8 (hard, symbolic).

Prove that the language $EXACT-COVER = {⟨ S_{1}, \dots, S_{m} ⟩ : there exist disjoint S_{i_{1}}, \dots, S_{i_{k}} whose union is S_{1} \cup \dots \cup S_{m}}$ is NP-complete by reducing 3SAT to it.

Answer

Given a 3CNF formula with variables $x_{1}, \dots, x_{n}$ and clauses $C_{1}, \dots, C_{k}$ , construct sets over the universe $U = {x_{1}, \dots, x_{n}, x_{1}^{'}, \dots, x_{n}^{'}, C_{1}, \dots, C_{k}}$ . For each variable $x_{i}$ : include set $T_{i} = {x_{i}} \cup {C_{j} : x_{i} appears in C_{j}}$ and set $F_{i} = {x_{i}^{'}} \cup {C_{j} : \neg x_{i} appears in C_{j}}$ . Each element $x_{i}$ and $x_{i}^{'}$ appears in exactly two sets ( $T_{i}$ and $F_{i}$ ), forcing an exact cover to choose exactly one of them (encoding the truth assignment). Each clause element $C_{j}$ appears in exactly the $T_{i}$ and $F_{i}$ sets for literals in $C_{j}$ , so it is covered iff at least one of its literals is set to true. The exact cover exists iff the formula is satisfiable. EXACT-COVER is in NP (verify by checking disjointness and coverage), so it is NP-complete.

Lean formalization Intermediate+

Mathlib has no formalisation of NP-completeness, the Cook-Levin theorem, or polynomial-time reductions between specific problems. The foundational gap is the absence of a verified reduction framework: a Complexity.PolynomialReduction structure with transitivity, and concrete instances for SAT-to-3SAT, 3SAT-to-CLIQUE, and CLIQUE-to-VERTEX-COVER. The Cook-Levin construction would require formalising the tableau encoding and the clause-generation algorithm. This unit ships without a lean_module.

Advanced results Master

Three directions extend the NP-completeness landscape.

Theorem 1 (thousands of NP-complete problems). Garey and Johnson's 1979 catalogue Computers and Intractability lists over 300 NP-complete problems across graph theory, number theory, algebra, combinatorics, and logic ^{[Sipser §7.5]}. The catalogue demonstrates that NP-completeness is not a rare property but a pervasive feature of combinatorial problems. Key additions include: 3-COLORING (chromatic number at most 3), KNAPSACK (the optimisation version of SUBSET-SUM), and LONGEST-PATH (does the graph have a simple path of length $\geq k$ ?).

Theorem 2 (strong NP-completeness). A problem is strongly NP-complete if it remains NP-complete even when all numerical inputs are bounded by a polynomial in the input length. SUBSET-SUM is NP-complete but not strongly NP-complete (it has a pseudopolynomial $O (n t)$ dynamic programming algorithm). 3-PARTITION (can $3 n$ numbers be partitioned into $n$ triples of equal sum?) is strongly NP-complete. The distinction matters for approximation: problems that are not strongly NP-complete often have efficient approximation schemes ^{[CLRS §34.5]}.

Theorem 3 (NP-completeness of approximate counting). Approximating the number of satisfying assignments of a SAT formula to within a factor of $2^{n^{1 - ε}}$ for any $ε > 0$ is NP-hard. This connects NP-completeness to the counting class $# P$ studied in 47.02.07, where the exact counting version of SAT ( $#$ SAT) is $# P$ -complete by Toda's theorem.

Synthesis. The collection of NP-complete problems is the foundational reason that P-vs-NP is the central question of computational complexity: the central insight is that thousands of seemingly different problems across mathematics and computer science are connected by a web of polynomial-time reductions, and this is exactly what makes a positive resolution of P-vs-NP so impactful. This builds toward the polynomial hierarchy in 47.02.04 where the NP level is extended by alternating quantifiers, and it appears again in 47.03.05 where the PCP theorem characterises NP by probabilistic proof checking. The generalises from individual reductions to a structural theory of computational hardness, and putting these together with the approximation results shows that NP-completeness has consequences even when we relax the requirement of exact solutions.

Full proof set Master

Proposition 1 (SAT to 3SAT reduction correctness). The standard clause-splitting reduction converts a SAT instance $ϕ$ to a 3SAT instance $ϕ^{'}$ such that $ϕ$ is satisfiable iff $ϕ^{'}$ is satisfiable.

Proof. For each clause $C = (l_{1} \lor \dots \lor l_{k})$ with $k > 3$ , replace with the gadget $(l_{1} \lor l_{2} \lor y_{1}) \land (\neg y_{1} \lor l_{3} \lor y_{2}) \land \dots \land (\neg y_{k - 3} \lor l_{k - 1} \lor l_{k})$ using fresh variables $y_{1}, \dots, y_{k - 3}$ .

Forward: if $C$ is satisfied by some $l_{m}$ , set $y_{1} = \dots = y_{m - 2} = true$ and $y_{m - 1} = \dots = y_{k - 3} = false$ . Clause $j$ for $j \leq m - 2$ is satisfied by $y_{j}$ ; clause $m - 1$ (if it exists) is satisfied by $l_{m}$ ; clauses $j > m - 1$ are satisfied by $\neg y_{j - 1}$ .

Backward: if the gadget is satisfied, at least one $l_{m}$ must be true. If all $l_{m}$ were false, then $y_{1} = true$ (from the first clause), $y_{2} = true$ (from the second), ..., $y_{k - 3} = true$ . But the last clause would be $(\neg y_{k - 3} \lor false \lor false) = false$ , a contradiction. $□$

Proposition 2 (CLIQUE to VERTEX-COVER reduction). $G$ has a clique of size $k$ iff $\overline{G}$ has a vertex cover of size $∣ V ∣ - k$ .

Proof. $S \subseteq V$ is a clique in $G$ iff every pair in $S$ has an edge in $G$ iff no pair in $S$ has a non-edge in $G$ iff every non-edge of $G$ has at least one endpoint in $V ∖ S$ iff $V ∖ S$ is a vertex cover of $\overline{G}$ (since non-edges of $G$ are edges of $\overline{G}$ ). The sizes match: $∣ V ∖ S ∣ = ∣ V ∣ - k$ . $□$

Connections Master

47.02.01 — The definitions of P, NP, and polynomial-time reductions provide the framework in which NP-completeness is defined.
47.02.02 — The Cook-Levin theorem (SAT is NP-complete) is the starting point for all NP-completeness proofs; every reduction chain begins with SAT.
47.02.04 — The polynomial hierarchy extends NP by alternating quantifiers; NP-complete problems are the base level $Σ_{1}^{p}$ .
47.04.04 — Bipartite matching is in P, contrasting with the NP-completeness of Hamiltonian cycle on general graphs.
47.02.07 — The counting class $# P$ asks how many solutions an NP problem has; $#$ SAT (count satisfying assignments) is $# P$ -complete.

Historical & philosophical context Master

Stephen Cook proved the NP-completeness of SAT in his 1971 paper "The Complexity of Theorem-Proving Procedures," presented at the ACM Symposium on Theory of Computing. He showed that any problem in NP can be encoded as a Boolean satisfiability problem, establishing SAT as the canonical NP-complete problem. Leonid Levin independently proved the same result in 1973 in the Soviet Union ^{[Sipser §7.4]}.

Richard Karp's 1972 paper "Reducibility Among Combinatorial Problems" transformed Cook's result from an isolated theorem into a practical tool. Karp showed that 21 fundamental problems — including CLIQUE, VERTEX-COVER, HAM-CYCLE, SUBSET-SUM, and 3-COLORING — are all NP-complete. His paper established the reduction methodology as the standard technique for proving NP-completeness and created the first map of the NP-complete landscape.

Garey and Johnson's 1979 book Computers and Intractability: A Guide to the Theory of NP-Completeness systematised the field, providing a catalogue of over 300 NP-complete problems and a standard format for NP-completeness proofs. Their appendix listing known NP-complete problems by problem domain remains a standard reference.

The philosophical significance of NP-completeness lies in the observation that many problems arising naturally in engineering, operations research, and mathematics are equivalent in difficulty to SAT. This provides strong evidence that P $\neq =$ NP, because resolving any one of these problems would resolve all of them simultaneously.

Bibliography Master

@book{sipser2013,
  author    = {Sipser, Michael},
  title     = {Introduction to the Theory of Computation},
  edition   = {3rd},
  publisher = {Cengage Learning},
  year      = {2013},
}
@book{clrs2022,
  author    = {Cormen, Thomas H. and Leiserson, Charles E. and Rivest, Ronald L. and Stein, Clifford},
  title     = {Introduction to Algorithms},
  edition   = {4th},
  publisher = {MIT Press},
  year      = {2022},
}
@inproceedings{cook1971complexity,
  author    = {Cook, Stephen A.},
  title     = {The Complexity of Theorem-Proving Procedures},
  booktitle = {Proceedings of the 3rd ACM Symposium on Theory of Computing},
  pages     = {151--158},
  year      = {1971},
}
@article{karp1972reducibility,
  author  = {Karp, Richard M.},
  title   = {Reducibility Among Combinatorial Problems},
  journal = {Complexity of Computer Computations},
  pages   = {85--103},
  year    = {1972},
  publisher = {Plenum Press},
}
@book{garey1979computers,
  author    = {Garey, Michael R. and Johnson, David S.},
  title     = {Computers and Intractability: A Guide to the Theory of NP-Completeness},
  publisher = {W. H. Freeman},
  year      = {1979},
}

Prerequisites

47.02.02 pending

Tier anchors

beginner: Sipser 2013 Introduction to the Theory of Computation 3e (Cengage) §7.4-7.5 (SAT is NP-complete, 3SAT, CLIQUE, VERTEX-COVER as NP-complete problems, polynomial-time reductions between them)
intermediate: Sipser 2013 Introduction to the Theory of Computation 3e (Cengage) §7.4-7.5; Cormen, Leiserson, Rivest & Stein 2022 Introduction to Algorithms 4e (MIT Press) §34.3-34.5 (NP-completeness proofs, reduction templates, gadget constructions)
master: Sipser 2013 Introduction to the Theory of Computation 3e (Cengage) §7.4-7.5; Cormen, Leiserson, Rivest & Stein 2022 Introduction to Algorithms 4e (MIT Press) §34.3-34.5; Garey & Johnson 1979 Computers and Intractability (Freeman) §2-3 (catalogue of NP-complete problems, reduction strategies, strong NP-completeness)

References

Sipser, M. — Introduction to the Theory of Computation (3rd ed.) · Cengage (2013). Section 7.4 proves the Cook-Levin theorem: $SAT$ is NP-complete by constructing, for any language $A \in NP$ and input $w$ , a Boolean formula $ϕ_{A, w}$ that is satisfiable iff a nondeterministic TM for $A$ accepts $w$ ; the formula encodes the tableau of the computation using variables $x_{i, j, t}$ meaning "cell $(i, j)$ of the tableau contains symbol $t$ ," with clauses enforcing valid transitions, start configuration, and an accept state. Section 7.5 reduces SAT to 3SAT (each clause of more than 3 literals is replaced by a gadget of 3-literal clauses using fresh variables), 3SAT to CLIQUE (create a triangle of vertices for each clause and connect non-conflicting vertices), and CLIQUE to VERTEX-COVER via the complement: $G$ has a clique of size $k$ iff $\overline{G}$ has a vertex cover of size $∣ V ∣ - k$ .
Cormen, T. H., Leiserson, R. L., Rivest, C. L. & Stein, C. — Introduction to Algorithms (4th ed.) · MIT Press (2022). Chapter 34.4 presents the Cook-Levin theorem and the circuit-SAT variant; Chapter 34.5 gives detailed NP-completeness proofs for CLIQUE, VERTEX-COVER, HAM-CYCLE, SUBSET-SUM, and the reduction from 3SAT to HAM-CYCLE via the subpath-forcing gadget (each variable gets a diamond-shaped subgraph and each clause gets a node that can be visited only if the corresponding literal is set to true).

Estimated time

beginner: 15m
intermediate: 40m
master: 75m