NP-Completeness

NP-completeness identifies the "hardest" problems in NP. If any one of them can be solved in polynomial time, ALL of NP can — and P = NP.

Polynomial-Time Reductions

A polynomial-time many-one reduction from A to B (A ≤_P B):

A computable function f: Σ* → Σ* such that:

1. f is computable in polynomial time.
2. x ∈ A iff f(x) ∈ B.

Meaning: B is at least as hard as A. If we can solve B in polynomial time, we can solve A in polynomial time (apply f first).

Reduction Design

To show B is NP-hard: reduce a known NP-hard problem A to B.

Known NP-hard problem A
    ↓ polynomial-time reduction f
Problem B (to prove NP-hard)

x ∈ A iff f(x) ∈ B

Key insight: The reduction transforms instances, not algorithms. You're showing that any algorithm for B could be used to solve A.

Cook-Levin Theorem

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

Proof Idea

Any NP language L has a polynomial-time verifier V(x, c). We construct a Boolean formula φ that is satisfiable iff V accepts (x, c) for some certificate c.

Construction: Encode the computation of V as a circuit:

• Variables for each bit of the certificate c.
• Variables for each cell of V's tape at each time step.
• Clauses encoding: initial configuration, transition function, acceptance.

The formula has polynomial size (polynomial time × polynomial space = polynomial number of variables and clauses).

Result: φ is satisfiable iff ∃c such that V(x, c) accepts iff x ∈ L.

From SAT to 3-SAT

SAT ≤_P 3-SAT: Any clause with > 3 literals can be split using auxiliary variables.

(a ∨ b ∨ c ∨ d ∨ e) becomes:
(a ∨ b ∨ z₁) ∧ (¬z₁ ∨ c ∨ z₂) ∧ (¬z₂ ∨ d ∨ e)

Each clause has ≤ 3 literals. The new formula is satisfiable iff the original is (z variables can be set appropriately).

NP-Complete Problems Catalog

Satisfiability Problems

SAT: Is a Boolean formula satisfiable?

3-SAT: SAT where every clause has exactly 3 literals. NP-complete.

2-SAT: Every clause has exactly 2 literals. In P (polynomial — implication graph + SCCs).

MAX-SAT: Maximize the number of satisfied clauses. NP-hard optimization.

Graph Problems

CLIQUE: Given G and k, does G have a complete subgraph of size k?

3-SAT ≤_P CLIQUE:
For each clause, create k vertices (one per literal per clause).
Connect vertices from different clauses unless they represent contradictory literals (x and ¬x).
k = number of clauses. Clique of size k = satisfying assignment.

VERTEX-COVER: Given G and k, is there a set of k vertices covering all edges?

CLIQUE ≤_P VERTEX-COVER:
G has a clique of size k iff the complement graph Ḡ has a vertex cover of size n-k.

INDEPENDENT-SET: Given G and k, is there a set of k pairwise non-adjacent vertices?

Complement of CLIQUE: independent set in G = clique in Ḡ.
Also: complement of VERTEX-COVER: IS of size k iff VC of size n-k.

HAMILTONIAN-CYCLE: Does G have a cycle visiting every vertex exactly once?

HAMILTONIAN-PATH: Does G have a path visiting every vertex exactly once?

GRAPH-COLORING (k ≥ 3): Can G be colored with k colors? 3-COLORING is NP-complete.

Number Problems

SUBSET-SUM: Given integers S and target t, is there a subset of S summing to t?

3-SAT ≤_P SUBSET-SUM (via clever encoding of clauses as digits in a number).

PARTITION: Can a set of integers be split into two subsets with equal sum? (Special case of SUBSET-SUM with t = total/2.)

KNAPSACK (decision version): Given items with weights/values and capacity W, is there a selection with total value ≥ V?

BIN-PACKING: Given n items with sizes and m bins with capacity C, can all items fit?

Other NP-Complete Problems

SET-COVER: Given a universe U and subsets S₁, ..., Sₙ, can k subsets cover U?

MAX-CUT: Given G, can vertices be split into two sets maximizing edges between them?

TRAVELING SALESMAN (decision): Is there a tour of length ≤ k?

INTEGER LINEAR PROGRAMMING: Is there an integer solution to a system of linear inequalities?

Reduction Techniques

Gadgets

Design small constructions (gadgets) that enforce constraints in the target problem.

Example (3-SAT → 3-COLORING):

• Variable gadget: Two connected nodes representing x and ¬x. One gets color T, the other F.
• Clause gadget: A small subgraph connected to the variable nodes. Colorable iff at least one literal in the clause is true (color T).
• Palette gadget: Three mutually connected nodes (T, F, Base) ensuring exactly three colors are used.

Component Design

For graph problems: design components that simulate logical operations (AND, OR, NOT) using the graph structure.

Local Replacement

For problems like HAMILTONIAN-CYCLE: replace each edge of a known NP-hard instance with a gadget subgraph that preserves the problem structure.

Proving NP-Completeness: Checklist

1. Show the problem is in NP: Give a polynomial-time verifier. What is the certificate? How do you verify it?

2. Choose a known NP-complete problem to reduce from. Pick one that's structurally similar to the target.

3. Design the reduction: Transform any instance of the known problem to an instance of the target problem in polynomial time.

4. Prove correctness: Show that YES instances of the known problem map to YES instances of the target, and NO instances map to NO instances (both directions).

5. Verify polynomial time: Ensure the reduction runs in polynomial time.

Common Reduction Sources

| Target Problem Type | Reduce From | |---|---| | Satisfiability-like | 3-SAT | | Graph coloring | 3-SAT or 3-COLORING | | Covering/packing | VERTEX-COVER, SET-COVER | | Subset selection | SUBSET-SUM, PARTITION | | Path/cycle | HAMILTONIAN-CYCLE | | Scheduling | PARTITION, 3-SAT | | Geometric | 3-SAT (with coordinate gadgets) |

Weak vs Strong NP-Hardness

Weakly NP-hard: NP-hard, but solvable in pseudo-polynomial time (polynomial in the numeric value of the input, not its bit-length).

Example: KNAPSACK is weakly NP-hard. The DP solution O(nW) is polynomial in W (the capacity value) but exponential in log W (the number of bits to represent W).

Strongly NP-hard: NP-hard even when all numbers in the input are bounded by a polynomial in the input length.

Example: 3-SAT, CLIQUE, HAMILTONIAN-CYCLE (no numbers involved), BIN-PACKING (strongly NP-hard).

FPTAS (Fully Polynomial-Time Approximation Scheme): Exists only for weakly NP-hard problems. Produces a (1+ε)-approximate solution in time polynomial in n and 1/ε. KNAPSACK has an FPTAS.

Applications in CS

• Problem classification: Knowing a problem is NP-complete tells you not to expect an efficient exact algorithm. Seek approximation, heuristics, or parameterized solutions.
• Complexity proofs: NP-completeness proofs are a standard tool in theoretical CS papers to establish computational hardness.
• Practice: Many real-world optimization problems (scheduling, routing, packing) are NP-hard. Use ILP solvers (Gurobi, CPLEX), SAT solvers, heuristics (simulated annealing, genetic algorithms), or exploit problem structure.
• Reductions as algorithms: Reducing to SAT and using a SAT solver is often the fastest way to solve small instances of NP-hard problems.