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.