NP-Completeness and Polynomial Reductions

NP-Completeness and Reductions: The Hardest Problems in NP

In 1972, Richard Karp published a paper listing 21 combinatorial problems. He proved they were all, in a precise mathematical sense, the same problem. Solve one efficiently, and you can solve all 21 efficiently. Fail to solve one, and you fail them all. These are the NP-complete problems — the hardest problems within NP, the ones that every other NP problem reduces to. Today, thousands of NP-complete problems are known across mathematics, biology, logistics, economics, and engineering. Understanding reductions — how one problem transforms into another — is the toolkit for recognising and handling this class of problems in practice.

Polynomial-Time Reductions

A polynomial-time reduction (Karp reduction) from problem L₁ to problem L₂, written L₁ ≤_p L₂, is a function f computable in polynomial time such that:

x ∈ L₁  ⟺  f(x) ∈ L₂

In other words: transform any instance of L₁ into an instance of L₂ in polynomial time, such that YES maps to YES and NO maps to NO. If L₁ ≤_p L₂:

• If L₂ is in P, then L₁ is in P (solving L₂ efficiently gives an efficient solver for L₁).
• If L₁ is NP-hard, then L₂ is NP-hard (if L₁ is universally hard, so is anything L₁ reduces to).

Reductions are transitive: if L₁ ≤_p L₂ and L₂ ≤_p L₃, then L₁ ≤_p L₃.

NP-Hard and NP-Complete

• NP-Hard: L is NP-hard if every problem in NP reduces to L in polynomial time. NP-hard problems are "at least as hard as everything in NP." They need not be in NP themselves (the Halting Problem is NP-hard but not in NP).
• NP-Complete: L is NP-complete if L is in NP AND L is NP-hard. NP-complete problems are exactly the hardest problems inside NP.

The Cook-Levin Theorem: Where NP-Completeness Began

Theorem (Cook, 1971; Levin, 1973): 3-SAT is NP-complete.

3-SAT: Given a Boolean formula in 3-CNF (3-conjunctive normal form — an AND of clauses, each clause being an OR of exactly 3 literals), does there exist a truth assignment to the variables that makes the formula true?

Example: Is (x₁ ∨ ¬x₂ ∨ x₃) ∧ (¬x₁ ∨ x₂ ∨ x₄) ∧ (x₂ ∨ ¬x₃ ∨ ¬x₄) satisfiable? A verifier checks any proposed assignment in O(n) time — 3-SAT is in NP. Cook proved it is NP-hard by showing that any NP problem can be encoded as a 3-SAT instance: the computation of a nondeterministic TM's accepting run becomes a Boolean formula. This was the first NP-completeness proof. Stephen Cook received the ACM Turing Award in 1982; Leonid Levin independently proved the equivalent result in the Soviet Union.

Karp's 21 NP-Complete Problems (1972)

Richard Karp's landmark paper "Reducibility Among Combinatorial Problems" established 21 problems as NP-complete by reduction chains:

Reduction Example: 3-SAT ≤_p Clique

Clique: Given a graph G and integer k, does G contain a clique (complete subgraph) of size k?

Reduction (Sipser, 2013, Theorem 7.32): Given a 3-CNF formula φ with k clauses, construct a graph G as follows:

1. For each clause (a ∨ b ∨ c), create three nodes labelled by the literals: (a,i), (b,i), (c,i) where i is the clause number.
2. Add an edge between (x,i) and (y,j) (i ≠ j) if the literals x and y are not complementary (x ≠ ¬y).
3. Claim: φ is satisfiable ⟺ G has a clique of size k.

Why it works: A satisfying assignment makes at least one literal true in each clause. Pick one true literal per clause — these k nodes form a clique (no two can be contradictory, since the same assignment satisfies both; and they're in different clauses, so all edges between them exist). Conversely, any k-clique selects one literal from each clause; assigning those literals true is consistent (no edge means no contradiction) and satisfies all k clauses.

This reduction runs in O(n²) time — clearly polynomial. Therefore: if Clique could be solved in polynomial time, 3-SAT could too — and since 3-SAT is NP-hard, so is Clique.

The Reductions Web

Handling NP-Complete Problems in Practice

Knowing a problem is NP-complete does not mean giving up. Four strategies exist:

1. Approximation algorithms: Find solutions guaranteed within a factor of optimal.

• Vertex Cover: a simple 2-approximation — repeatedly pick any uncovered edge, add both endpoints, O(E).
• TSP with triangle inequality: Christofides-Serdyukov algorithm gives a 1.5× approximation, O(n³).
• Bin Packing: First-Fit Decreasing gives ≤ (11/9)OPT + 6/9 items.

2. Exact exponential algorithms with good average case: SAT solvers.

• MiniSAT, CaDiCaL, and Glucose are industrial SAT solvers that handle formulas with millions of variables using DPLL + CDCL (Conflict-Driven Clause Learning).
• Used in hardware verification (Intel, AMD), AI planning, cryptanalysis, and software model checking.
• Worst-case: exponential. Average case: often polynomial in practice for structured instances.

3. Heuristics: No worst-case guarantee but fast in practice.

• Genetic algorithms, simulated annealing, tabu search for TSP and scheduling.
• Modern TSP solvers (Concorde) routinely solve instances with tens of thousands of cities to optimality using branch-and-bound.

4. Fixed-parameter tractable (FPT) algorithms: Exponential only in a small parameter k, polynomial in input size n.

• Vertex Cover: solvable in O(2^k × n) — if k is small, this is fast even for large n.
• Many graph problems become tractable when restricted to graphs of bounded treewidth.

Why This Matters

NP-completeness is the practitioner's red flag. When you can show that your optimisation problem is NP-complete — by reducing a known NP-complete problem to it in polynomial time — you know three things immediately: (1) no one has found a polynomial algorithm in 50+ years of trying; (2) you should look for approximation or heuristic approaches rather than exact polynomial solutions; (3) if you DO find a polynomial algorithm, you have solved P vs. NP and won $1,000,000.

The ability to recognise NP-complete structure in real problems — logistics, scheduling, genome assembly, circuit layout, network design — and to apply the right approximate or heuristic strategy, is one of the most practically valuable skills that comes from studying theoretical computer science.

Sources: Cook, S. A. (1971). The complexity of theorem-proving procedures. Proceedings of the 3rd Annual ACM Symposium on Theory of Computing, 151–158. | Karp, R. M. (1972). Reducibility among combinatorial problems. In R. E. Miller & J. W. Thatcher (Eds.), Complexity of Computer Computations (pp. 85–103). Plenum Press. | Sipser, M. (2013). Introduction to the Theory of Computation (3rd ed.). Cengage. | Christofides, N. (1976). Worst-case analysis of a new heuristic for the travelling salesman problem. Carnegie Mellon University Technical Report.