NP-completeness: Cook–Levin and classic reductions

Lesson 8 defined NP-completeness and showed how reductions transfer hardness. This lesson produces the first NP-complete problem and then grows a family tree of others by reductions. The root is the Cook–Levin theorem: Boolean satisfiability is NP-complete. From satisfiability we reach 3SAT, independent set, vertex cover, clique, set cover, subset sum, knapsack, Hamiltonian cycle and the travelling salesperson problem. The reductions use small structures called gadgets that imitate the logic of one problem inside another. Seeing several of them is the best way to learn to build your own, and the proofs all follow the same two-direction pattern from lesson 6.

The first NP-complete problem

It is easiest to start with circuits. A Boolean circuit is a directed acyclic graph of AND, OR and NOT gates with some input wires and one output. CIRCUIT-SAT asks whether some setting of the inputs makes the output 1. It is clearly in NP: the input setting is a certificate, and evaluating the circuit gate by gate takes linear time. Theorem (Cook 1971, Levin 1973). CIRCUIT-SAT is NP-hard. Proof sketch. Let X be any problem in NP, with a verifier V that runs in time \(p(n)\) on an instance x and a certificate c of length at most \(p(n)\). A computer running V for \(p(n)\) steps is a fixed piece of hardware: its memory at each step is a finite array of bits, and the contents at step \(t + 1\) are a fixed Boolean function of the contents at step t. Unroll the computation into \(p(n)\) layers of copies of the processor's logic, each layer computing the next memory state from the previous one, with a polynomial number of gates per layer. Hard-wire the bits of x into the first layer, leave the bits of c as the circuit's inputs, and let the output be V's accept bit at the end. The circuit has polynomial size, can be written down in polynomial time, and is satisfiable exactly when some certificate makes V accept, that is, exactly when x is a yes-instance.

Two points in this sketch carry the weight. First, locality: one step of computation changes only a bounded amount of state and depends on a bounded amount, so each layer is a small circuit. Second, the certificate is polynomially long, so the circuit has polynomially many inputs. The formal proof in CMPUT-474 replaces 'a computer' by a Turing machine and the layers by a tableau of configurations, but the idea is the same. Cook's 1971 paper used this argument for satisfiability of formulas; Levin found it independently in the Soviet Union, in a paper published in 1973.

From circuits to formulas

SAT asks whether a formula in conjunctive normal form (CNF), an AND of clauses each of which is an OR of literals, has a satisfying assignment. To reduce CIRCUIT-SAT to SAT, a naive approach would expand the circuit into one big formula, but shared subcircuits would be copied over and over, possibly exponentially. The Tseitin transformation (1968) avoids this by introducing a new variable \(g\) for each gate and adding a few clauses that force g to equal the gate's output. For an AND gate \(g = x \land y\), the clauses \((\bar g \lor x)\), \((\bar g \lor y)\) and \((g \lor \bar x \lor \bar y)\) say exactly that. Add a unit clause asserting the output variable. The formula has one variable per wire and a constant number of clauses per gate, and it is satisfiable exactly when the circuit is: a satisfying input determines the values of all wires, and conversely any model of the clauses describes a consistent evaluation with output 1.

# CIRCUIT-SAT to SAT (the Tseitin transformation): one new variable per gate,
# and a few clauses forcing it to equal the gate's output. Size stays linear in the circuit.
from itertools import product

# Circuit: inputs a, b, c.  g1 = a AND b,  g2 = NOT c,  g3 = g1 OR g2,  g4 = a XOR c,  out = g3 AND g4
gates = [("g1", "and", "a", "b"), ("g2", "not", "c", None), ("g3", "or", "g1", "g2"),
         ("g4", "xor", "a", "c"), ("out", "and", "g3", "g4")]
names = ["a", "b", "c"] + [g[0] for g in gates]
var = {v: i + 1 for i, v in enumerate(names)}

def clauses_for(g, op, x, y):
    G, X = var[g], var[x]
    if op == "not": return [(-G, -X), (G, X)]
    Y = var[y]
    if op == "and": return [(-G, X), (-G, Y), (G, -X, -Y)]
    if op == "or":  return [(G, -X), (G, -Y), (-G, X, Y)]
    if op == "xor": return [(-G, X, Y), (-G, -X, -Y), (G, -X, Y), (G, X, -Y)]

cnf = [c for g in gates for c in clauses_for(*g)] + [(var["out"],)]   # require output = 1
print("CNF has", len(var), "variables and", len(cnf), "clauses")

def circuit(a, b, c):
    v = {"a": a, "b": b, "c": c}
    for g, op, x, y in gates:
        v[g] = {"and": lambda: v[x] and v[y], "or": lambda: v[x] or v[y],
                "xor": lambda: v[x] != v[y], "not": lambda: not v[x]}[op]()
    return v["out"]

sat_inputs = [t for t in product([False, True], repeat=3) if circuit(*t)]
models = [m for m in product([False, True], repeat=len(var))
          if all(any((l > 0) == m[abs(l) - 1] for l in cl) for cl in cnf)]
print("circuit is satisfied by inputs (a, b, c):", sat_inputs)
print("CNF models restricted to a, b, c:        ", sorted({m[:3] for m in models}))
print("each satisfying input extends to exactly one model:", len(models) == len(sat_inputs))

CNF has 8 variables and 16 clauses
circuit is satisfied by inputs (a, b, c): [(True, False, False), (True, True, False)]
CNF models restricted to a, b, c:         [(True, False, False), (True, True, False)]
each satisfying input extends to exactly one model: True

From SAT to 3SAT

3SAT restricts every clause to exactly three literals. It is still NP-complete. Given a CNF formula, pad short clauses by repeating a literal, and split a long clause \((l_1 \lor l_2 \lor \cdots \lor l_k)\) with \(k > 3\) into a chain using fresh variables \(z_1, \dots, z_{k-3}\): \((l_1 \lor l_2 \lor z_1) \land (\bar z_1 \lor l_3 \lor z_2) \land \cdots \land (\bar z_{k-3} \lor l_{k-1} \lor l_k)\). If some \(l_i\) is true, set the z variables before it to true and those after it to false; every chain clause is then satisfied. If all \(l_i\) are false, the first clause forces \(z_1\), which forces \(z_2\), and so on, until the last clause is false. So the chain is satisfiable, with suitable z values, exactly when the original clause is. The reduction is linear in the size of the formula. With two literals per clause, by contrast, satisfiability is decidable in linear time using strongly connected components of an implication graph; three is the threshold.

# SAT to 3SAT: split long clauses with fresh variables, pad short ones.
#   (l1 or l2 or ... or lk)  ->  (l1 or l2 or z1)(-z1 or l3 or z2) ... (-z_{k-3} or l_{k-1} or lk)
import random
from itertools import product
random.seed(304)

def to3(cnf, n):
    out, nxt = [], n + 1
    for c in cnf:
        if len(c) == 1: c = (c[0], c[0], c[0])
        if len(c) == 2: c = (c[0], c[0], c[1])
        if len(c) == 3: out.append(tuple(c)); continue
        z = nxt; nxt += 1
        out.append((c[0], c[1], z))
        for lit in c[2:-2]:
            out.append((-z, lit, nxt)); z = nxt; nxt += 1
        out.append((-z, c[-2], c[-1]))
    return out, nxt - 1

def satisfiable(cnf, n):
    return any(all(any((l > 0) == a[abs(l) - 1] for l in c) for c in cnf)
               for a in product([False, True], repeat=n))

for trial in range(300):
    n = random.randint(2, 5)
    cnf = [tuple(random.choice([-1, 1]) * random.randint(1, n) for _ in range(random.randint(1, 6)))
           for _ in range(random.randint(1, 6))]
    c3, m = to3(cnf, n)
    assert all(len(c) == 3 for c in c3)
    assert satisfiable(cnf, n) == satisfiable(c3, m)
print("300 random formulas: the 3-CNF is satisfiable exactly when the original is")
c3, m = to3([(1, -2, 3, 4, -5, 6)], 6)
print("example: a 6-literal clause becomes", c3)

300 random formulas: the 3-CNF is satisfiable exactly when the original is
example: a 6-literal clause becomes [(1, -2, 7), (-7, 3, 8), (-8, 4, 9), (-9, -5, 6)]

From 3SAT to independent set

Given a 3-CNF formula with m clauses, build a graph with one vertex for each literal occurrence, three per clause. Join the three vertices of each clause into a triangle, and join every pair of vertices labelled with complementary literals \(x_i\) and \(\bar x_i\). Ask for an independent set of size \(k = m\). If the formula is satisfiable: fix a satisfying assignment and choose one true literal from each clause. No two chosen vertices are in the same triangle, and no two are complementary because both are true. So they form an independent set of size m. If the graph has an independent set of size m: it contains at most one vertex per triangle, so exactly one per clause. It never contains both \(x_i\) and \(\bar x_i\), so setting the chosen literals true gives a consistent partial assignment, and extending it arbitrarily satisfies every clause. Since independent set reduces to vertex cover and clique (lesson 8), all three are NP-complete.

# 3SAT to INDEPENDENT-SET on the formula of the figure:
#   (x1 or -x2 or x3) and (-x1 or x2 or x3) and (x1 or x2 or -x3)
from itertools import combinations, product
phi = [(1, -2, 3), (-1, 2, 3), (1, 2, -3)]
V = [(ci, lit) for ci, c in enumerate(phi) for lit in c]          # one vertex per literal occurrence
E = [(u, v) for u, v in combinations(V, 2) if u[0] == v[0] or u[1] == -v[1]]
k = len(phi)
print(len(V), "vertices,", len(E), "edges, k =", k)
print(sum(u[0] == v[0] for u, v in E), "triangle edges and", sum(u[0] != v[0] for u, v in E), "conflict edges")
sets = [S for S in combinations(V, k) if not any((a, b) in E or (b, a) in E for a, b in combinations(S, 2))]
assigns = [a for a in product([False, True], repeat=3) if all(any((l > 0) == a[abs(l) - 1] for l in c) for c in phi)]
print("independent sets of size 3:", len(sets), "  satisfying assignments:", len(assigns))
S = sets[0]
print("for example the set", [f"clause {c + 1}: {'x' if l > 0 else '-x'}{abs(l)}" for c, l in S])
truth = {abs(l): l > 0 for _, l in S}
print("gives the partial assignment", truth, "- unset variables may take either value")

9 vertices, 15 edges, k = 3
9 triangle edges and 6 conflict edges
independent sets of size 3: 12   satisfying assignments: 5
for example the set ['clause 1: x1', 'clause 2: x2', 'clause 3: x1']
gives the partial assignment {1: True, 2: True} - unset variables may take either value

From 3SAT to subset sum: numbers as gadgets

Reductions to number problems encode logic in digits. Given a 3-CNF formula with n variables and m clauses, build numbers written in base 10 with \(n + m\) digit positions. For each variable \(x_i\), create two numbers \(t_i\) and \(f_i\), each with a 1 in the column of variable i; \(t_i\) also has a 1 in each clause column where \(x_i\) occurs, and \(f_i\) in each clause column where \(\bar x_i\) occurs. For each clause create two slack numbers with a 1 or a 2 in its column. The target has a 1 in every variable column and a 4 in every clause column. Since each column receives at most 6 from all numbers together, no carries occur, so each column can be analysed separately. A variable column forces exactly one of \(t_i, f_i\), which is a truth assignment. A clause column receives one unit per true literal, between 0 and 3, and the slack numbers can add 1, 2 or 3 but not 4, so the column reaches 4 exactly when at least one literal is true. Hence a subset sums to the target exactly when the formula is satisfiable.

# 3SAT to SUBSET-SUM with base-10 digits: one digit column per variable, one per clause.
# Variable i gives numbers t_i (x_i true) and f_i (x_i false), each with a 1 in column i
# and a 1 in each clause column where the literal appears. Clause slack numbers 1 and 2 let a
# clause column reach 4 when 1, 2 or 3 of its literals are true. Target: 1...1 4...4.
from itertools import product, combinations

def reduce(phi, n):
    m = len(phi)
    def num(var_col, clause_digits):
        d = [0] * (n + m)
        if var_col is not None: d[var_col] = 1
        for j, x in clause_digits: d[n + j] += x
        return int("".join(map(str, d)))
    nums = []
    for i in range(1, n + 1):
        nums.append(num(i - 1, [(j, 1) for j, c in enumerate(phi) if i in c]))     # t_i
        nums.append(num(i - 1, [(j, 1) for j, c in enumerate(phi) if -i in c]))    # f_i
    for j in range(m):
        nums += [num(None, [(j, 1)]), num(None, [(j, 2)])]
    target = int("1" * n + "4" * m)
    return nums, target

def sat(phi, n):
    return any(all(any((l > 0) == a[abs(l) - 1] for l in c) for c in phi) for a in product([0, 1], repeat=n))
def subset_sum(nums, T):
    reach = {0}
    for x in nums: reach |= {s + x for s in reach if s + x <= T}
    return T in reach

phi = [(1, -2, 3), (-1, 2, 3), (1, 2, -3)]
nums, T = reduce(phi, 3)
print("numbers:", nums)
print("target: ", T)
print("phi satisfiable:", sat(phi, 3), "  subset sum reachable:", subset_sum(nums, T))
psi = [(1, 1, 2), (-1, -1, 2), (1, 1, -2), (-1, -1, -2)]          # unsatisfiable
nums, T = reduce(psi, 2)
print("psi satisfiable:", sat(psi, 2), "  subset sum reachable:", subset_sum(nums, T))

numbers: [100101, 100010, 10011, 10100, 1110, 1001, 100, 200, 10, 20, 1, 2]
target:  111444
phi satisfiable: True   subset sum reachable: True
psi satisfiable: False   subset sum reachable: False

Subset sum reduces in turn to partition, splitting numbers into two halves of equal sum (add two numbers that balance the target), and to knapsack (set each value equal to its weight and both the capacity and the value goal to T). So knapsack is NP-complete, which matches lesson 3: its \(O(nW)\) algorithm is pseudo-polynomial, and the numbers built by this reduction are exponentially large in the formula size. Problems that stay NP-complete even when numbers are written in unary, such as vertex cover, TSP with small distances or 3-partition, are called strongly NP-complete; they have no pseudo-polynomial algorithms unless P = NP.

Hamiltonian cycle and the travelling salesperson problem

Karp's 1972 paper showed that Hamiltonian cycle is NP-complete by a chain of reductions; a direct reduction from 3SAT uses one gadget per variable, a long path of vertices that can be traversed left to right (true) or right to left (false), stacked so that a Hamiltonian cycle passes through them in order, and one vertex per clause that can be visited by a short detour from a variable path only in the direction that makes the corresponding literal true. A Hamiltonian cycle then corresponds exactly to a satisfying assignment. Lesson 8 reduced Hamiltonian cycle to TSP with distances 1 and 2, so TSP is NP-hard, even when distances satisfy the triangle inequality.

Integer programming and Karp's list

Integer linear programming is NP-hard by an almost trivial reduction: for each clause \((l_1 \lor l_2 \lor l_3)\) write a constraint that the sum of its literals is at least 1, with \(x_i\) for a positive literal and \(1 - x_i\) for a negative one, and require each \(x_i \in \{0, 1\}\). In 1972 Richard Karp published Reducibility among combinatorial problems, showing 21 problems NP-complete with a tree of reductions much like the figure above, including clique, set cover, vertex cover, Hamiltonian cycle, 0/1 integer programming, knapsack and max cut. That paper turned Cook's theorem from a curiosity about logic into a tool for every area of computing; Karp received the Turing Award in 1985, and Cook in 1982.

How to prove a problem NP-complete

The checklist is short. (1) Membership: describe a certificate of polynomial length and a polynomial-time verifier. (2) Choose a source problem that is known to be NP-complete and resembles the new one: 3SAT for problems with logical choices, vertex cover or independent set for graph selection problems, subset sum for number problems, Hamiltonian cycle for ordering problems. (3) Build the instance in polynomial time, usually from gadgets for the variables and constraints of the source. (4) Prove both directions: a yes-instance of the source gives a yes-instance of the target, and a yes-instance of the target gives back a yes-instance of the source. (5) Check the size of the construction, including the size of any numbers. The commonest error is step 4's second direction: the target instance must not have solutions that do not correspond to anything in the source.

Worked examples