NP-completeness: how SAT, 3-COLOR, and TSP are secretly the same problem

P, NP, and NP-hard

P is the class of decision problems solvable in polynomial time. NP is the class of decision problems whose solutions can be verified in polynomial time — even if finding one might take exponentially long. Every problem in P is trivially in NP (if you can solve it fast, you can verify a solution fast), but whether P = NP is the most famous open problem in computer science.

A problem is NP-hard if every problem in NP can be reduced to it in polynomial time — informally, it's "at least as hard as anything in NP." A problem that is both NP-hard and itself in NP is NP-complete.

Polynomial-time reductions

A polynomial-time reduction from problem A to problem B (written A ≤ₚ B) is a polynomial-time algorithm that transforms any instance of A into an instance of B, such that the answer to B's instance tells you the answer to A's instance. The key logical consequence:

This is exactly the strategy used to prove new problems are NP-complete: don't design an algorithm from scratch, instead show that a known NP-complete problem reduces to it.

Cook-Levin: SAT is NP-complete

The Cook-Levin theorem (1971) is the seed of the entire reduction tree: it proves that Boolean satisfiability (SAT) is NP-complete directly, by simulating an arbitrary polynomial-time nondeterministic Turing machine's computation history as a giant Boolean formula. Any accepting computation of the machine corresponds to a satisfying assignment, and vice versa.

3-SAT — where every clause has exactly 3 literals — is also NP-complete (SAT reduces to 3-SAT by splitting long clauses with auxiliary variables), and is the most common starting point for reductions because its uniform structure is easy to encode into other combinatorial problems.

Reducing 3-SAT to 3-COLOR

Graph 3-coloring asks: can the vertices of a graph be colored with 3 colors such that no edge connects two vertices of the same color? The classic reduction from 3-SAT builds three gadgets:

1. Base triangle: three special vertices T (True), F (False), B (Base), mutually connected, fixing three distinct "reference colors."
2. Variable gadget: for each variable xᵢ, a triangle {xᵢ, x̄ᵢ, B} forces xᵢ and x̄ᵢ to take the T or F color — but never the same one, exactly encoding "xᵢ is true XOR xᵢ is false."
3. Clause gadget (OR-gadget): for each clause (a ∨ b ∨ c), a small 6-vertex gadget connected to literals a, b, c and to the T/F vertices, constructed so that it is 3-colorable if and only if at least one of a, b, c is colored T.

Reducing 3-SAT to TSP (via Hamiltonian cycle)

The Traveling Salesman Problem (decision version: "is there a tour of length ≤ k?") is usually shown NP-hard in two steps: 3-SAT reduces to Hamiltonian Cycle (does a cycle visiting every vertex exactly once exist?), and Hamiltonian Cycle reduces trivially to TSP.

Step 1 — Hamiltonian Cycle reduces to TSP

Given a graph G, build a complete weighted graph G' on the same vertices: edges present in G get weight 1, all other edges get weight 2. G has a Hamiltonian cycle if and only if G' has a tour of total weight exactly n (using only weight-1 edges):

Step 2 — 3-SAT reduces to Hamiltonian Cycle

This reduction (due to Karp, 1972) is intricate: each variable xᵢ is represented by a "twisted ladder" gadget with two possible traversal directions (corresponding to xᵢ = True or False), and each clause is represented by a connector vertex that can only be visited by "borrowing" a pass from one of its three literal gadgets — forcing at least one literal per clause to be traversed in the "satisfying" direction.

What NP-completeness means in practice

Proving a problem NP-complete is not a dead end — it's actionable information. It tells you:

• Don't waste time hunting for a polynomial exact algorithm — thousands of researchers have tried on related problems since the 1970s without success.
• An exponential worst-case exact algorithm (branch-and-bound, DPLL for SAT) may still be fine for the instance sizes you actually care about.
• Approximation algorithms with provable guarantees exist for many NP-hard optimization problems (e.g. Christofides' 1.5-approximation for metric TSP).
• Special-case structure (planar graphs, bounded treewidth, small clause density) can make otherwise-hard instances tractable.

Living with NP-hardness: heuristics

For instances too large for exact methods, practitioners reach for heuristics that trade optimality guarantees for speed: