P, NP and polynomial-time reductions

The first seven lessons were about finding efficient algorithms. Some problems have resisted every attempt: no polynomial-time algorithm is known for the travelling salesperson problem, for vertex cover, for the knapsack problem with large numbers, or for Boolean satisfiability, despite decades of work by very good people. The theory of NP-completeness, created by Stephen Cook, Leonid Levin and Richard Karp in the early 1970s, does not prove that these problems are hard. It proves something almost as useful: that they are all equally hard, in the sense that a polynomial-time algorithm for any one of them would give polynomial-time algorithms for all of them, and for thousands of other problems. This lesson sets up the classes P and NP and the central tool, the polynomial-time reduction. Lesson 9 proves that specific problems are NP-complete. CMPUT-474 later gives the formal treatment with Turing machines and nondeterminism.

Decision problems and the class P

To compare problems precisely we work with decision problems, whose answer is yes or no. Lesson 1 showed that this loses little: optimization versions are polynomially equivalent to their decision versions for the problems in this course. An instance of a decision problem is encoded as a string, and the problem is identified with the set of strings whose answer is yes. Encodings must be reasonable: numbers in binary, graphs as adjacency lists or matrices. Writing a number in unary would make pseudo-polynomial algorithms look polynomial. P is the class of decision problems solvable by an algorithm whose running time is \(O(n^k)\) for some constant k, where n is the length of the encoded input. Everything from lessons 2 to 7, in decision form, lies in P.

Certificates and the class NP

For many hard problems, a yes answer can be checked quickly if someone supplies the right evidence. If a graph has a vertex cover of size at most k, the cover itself convinces us: check its size and check every edge. If a travelling salesperson instance has a tour of length at most B, the tour convinces us. The evidence is called a certificate or witness, and the checking procedure a verifier. Definition. A decision problem X is in NP if there is a polynomial-time algorithm V and a polynomial p such that for every instance x: if x is a yes-instance, there is a certificate c with \(|c| \le p(|x|)\) such that \(V(x, c)\) accepts; and if x is a no-instance, \(V(x, c)\) rejects for every c. The name stands for nondeterministic polynomial time, from the equivalent definition by machines that can guess the certificate; it does not mean 'not polynomial'.

# Verifiers: polynomial-time checks of a proposed certificate for three NP problems.
def verify_vertex_cover(edges, k, C):
    return len(set(C)) <= k and all(u in C or v in C for u, v in edges)

def verify_tsp(D, B, tour):
    n = len(D)
    return (sorted(tour) == list(range(n)) and
            sum(D[tour[i]][tour[(i + 1) % n]] for i in range(n)) <= B)

def verify_partition(nums, half):
    idx = set(half)
    return 2 * sum(nums[i] for i in idx) == sum(nums) and idx <= set(range(len(nums)))

E = [(0, 1), (0, 2), (1, 2), (2, 3), (3, 4), (2, 4)]
print("vertex cover {0, 2, 3} of size <= 3:", verify_vertex_cover(E, 3, {0, 2, 3}))
print("vertex cover {1, 2, 4} of size <= 3:", verify_vertex_cover(E, 3, {1, 2, 4}))
print("vertex cover {0, 4} of size <= 2:  ", verify_vertex_cover(E, 2, {0, 4}))
D = [[0, 7, 4, 9, 5], [7, 0, 3, 6, 8], [4, 3, 0, 5, 6], [9, 6, 5, 0, 4], [5, 8, 6, 4, 0]]
print("tour 0-2-1-3-4 of length <= 22:", verify_tsp(D, 22, [0, 2, 1, 3, 4]))
print("tour 0-1-2-3-4 of length <= 22:", verify_tsp(D, 22, [0, 1, 2, 3, 4]))
nums = [8, 3, 11, 5, 9, 4, 6, 2]
print("partition using items {0, 2, 3}:   ", verify_partition(nums, [0, 2, 3]))
print("partition using items {0, 2, 5, 7}:", verify_partition(nums, [0, 2, 5, 7]))

vertex cover {0, 2, 3} of size <= 3: True
vertex cover {1, 2, 4} of size <= 3: True
vertex cover {0, 4} of size <= 2:   False
tour 0-2-1-3-4 of length <= 22: True
tour 0-1-2-3-4 of length <= 22: False
partition using items {0, 2, 3}:    True
partition using items {0, 2, 5, 7}: False

The definition is asymmetric. Certificates show that the answer is yes; for a no-instance, nothing needs to convince anyone. The class of problems whose no-instances have short certificates is co-NP. For example, 'does this formula have no satisfying assignment?' is in co-NP, and it is not known to be in NP: what short evidence could prove that none of \(2^n\) assignments works? Some problems are in both: deciding whether a number has a factor below a bound is in NP (the factor is a certificate) and in co-NP (the prime factorization is a certificate for no). Whether \(\text{NP} = \text{co-NP}\) is open, and most researchers believe not.

How P, NP and exponential time relate

P is contained in NP. If X is solvable in polynomial time, a verifier can ignore the certificate and solve the instance itself. NP is contained in EXP, the class of problems solvable in time \(2^{O(n^k)}\). Given a verifier V with certificate bound \(p(n)\), try all \(2^{p(n)}\) possible certificates and run V on each; accept if any succeeds. This brute-force search is exactly what we want to avoid, and it is all we know how to do in general. The central question of the field is whether the first inclusion is strict: does P equal NP? In words, is every problem whose solutions can be checked quickly also solvable quickly? It is one of the seven Millennium Prize Problems of the Clay Mathematics Institute, each carrying a prize of one million US dollars, and it remains open as of 2026.

# NP is contained in EXP: try every certificate. For PARTITION a certificate is a subset,
# so a verifier-based search examines up to 2^n certificates, each checked in polynomial time.
import random
random.seed(304)

def partition_search(nums):
    n, total, tried = len(nums), sum(nums), 0
    if total % 2: return False, 0
    for mask in range(2 ** (n - 1)):                 # item n-1 can be put on the other side
        tried += 1
        if 2 * sum(nums[i] for i in range(n - 1) if mask >> i & 1) == total:
            return True, tried
    return False, tried

print(" n   answer   certificates tried")
for n in (8, 12, 16, 20):
    nums = [random.randrange(2, 10 ** 6, 2) for _ in range(n - 1)] + [10 ** 9]   # one huge item:
    # the total is even, but no subset can balance the huge item, so this is a no-instance
    ans, tried = partition_search(nums)
    print(f"{n:2d}   {ans!s:6s}   {tried:18d}")

 n   answer   certificates tried
 8   False                   128
12   False                  2048
16   False                 32768
20   False                524288

Polynomial-time reductions

A problem X reduces to a problem Y in polynomial time, written \(X \le_p Y\), if there is a polynomial-time algorithm f that transforms every instance x of X into an instance \(f(x)\) of Y such that x is a yes-instance of X if and only if \(f(x)\) is a yes-instance of Y. (This is a Karp or many-one reduction. A Cook reduction allows polynomially many calls to a subroutine for Y; for our purposes the Karp version suffices.) Reductions are not new to you: lesson 6 reduced matching, disjoint paths and project selection to flow, and lesson 7 reduced flow to linear programming. Those reductions were used to solve problems. The same tool also transfers hardness.

Lemma. If \(X \le_p Y\) and \(Y \in \text{P}\), then \(X \in \text{P}\). Proof. On input x, compute \(f(x)\) in time \(q(|x|)\) for a polynomial q; its length is at most \(q(|x|)\) since the algorithm writes at most one symbol per step. Then run Y's algorithm, taking time \(r(q(|x|))\), a polynomial in \(|x|\). Read contrapositively: if X is not in P, then neither is Y. So a reduction from X to Y shows that Y is at least as hard as X. The direction matters and is easy to get backwards. To show a new problem Y is hard, reduce a problem known to be hard to Y. Reductions also compose: if \(X \le_p Y\) and \(Y \le_p Z\), then \(X \le_p Z\), since a polynomial of a polynomial is a polynomial.

First reductions: independent set, vertex cover and clique

An independent set in a graph is a set of vertices no two of which are adjacent; a clique is a set every two of which are adjacent; a vertex cover is a set touching every edge. Claim 1. S is independent in \(G = (V, E)\) if and only if \(V \setminus S\) is a vertex cover. Proof. S is independent iff no edge has both endpoints in S, iff every edge has at least one endpoint outside S, iff \(V \setminus S\) covers every edge. So \((G, k) \mapsto (G, n - k)\) reduces INDEPENDENT-SET to VERTEX-COVER, and the same map reduces VERTEX-COVER back to INDEPENDENT-SET. Claim 2. S is independent in G if and only if S is a clique in the complement graph \(\bar G\), which has an edge exactly where G does not. So \((G, k) \mapsto (\bar G, k)\) reduces INDEPENDENT-SET to CLIQUE and back. All three problems are therefore equally hard up to polynomial factors.

# Three classic polynomial-time reductions, verified exhaustively on random small graphs:
#   INDEPENDENT-SET(G, k)  <=>  VERTEX-COVER(G, n - k)  <=>  CLIQUE(complement of G, k)
import random
from itertools import combinations
random.seed(304)

def has_is(n, E, k):
    return any(all((u, v) not in E and (v, u) not in E for u, v in combinations(S, 2))
               for S in combinations(range(n), k))
def has_vc(n, E, k):
    return any(all(u in C or v in C for u, v in E) for C in combinations(range(n), k))
def has_clique(n, E, k):
    return any(all((u, v) in E or (v, u) in E for u, v in combinations(S, 2))
               for S in combinations(range(n), k))
def complement(n, E):
    return {(u, v) for u, v in combinations(range(n), 2) if (u, v) not in E and (v, u) not in E}

checked = 0
for trial in range(300):
    n = random.randint(2, 8)
    E = {(u, v) for u, v in combinations(range(n), 2) if random.random() < 0.45}
    for k in range(n + 1):
        a, b, c = has_is(n, E, k), has_vc(n, E, n - k), has_clique(n, complement(n, E), k)
        assert a == b == c
        checked += 1
print("checked", checked, "instances: IS(G, k) = VC(G, n-k) = CLIQUE(complement, k) every time")

checked 1826 instances: IS(G, k) = VC(G, n-k) = CLIQUE(complement, k) every time

More reductions

VERTEX-COVER reduces to SET-COVER. In SET-COVER we are given a universe U, a family of subsets of U and a number k, and ask whether k of the subsets cover U. Given a graph, let U be its edge set and, for each vertex v, let \(S_v\) be the set of edges at v. A vertex cover of size k is exactly k sets \(S_v\) covering all edges. HAMILTONIAN-CYCLE reduces to TSP. Given a graph G on n vertices, build a TSP instance on the same vertices with distance 1 for pairs that are edges of G and 2 for pairs that are not, and bound \(B = n\). A tour has n legs, each of length at least 1, so it has length at most n exactly when every leg is an edge of G, that is, when it is a Hamiltonian cycle. So if TSP had a polynomial algorithm, so would Hamiltonian cycle.

# HAMILTONIAN-CYCLE reduces to TSP: weight 1 for edges of G, weight 2 for non-edges.
# G has a Hamiltonian cycle  <=>  the TSP instance has a tour of length <= n.
import random
from itertools import permutations, combinations
random.seed(304)

def ham(n, E):
    return any(all(frozenset((p[i], p[(i + 1) % n])) in E for i in range(n))
               for p in ((0,) + q for q in permutations(range(1, n))))
def tsp_at_most(D, B):
    n = len(D)
    return any(sum(D[p[i]][p[(i + 1) % n]] for i in range(n)) <= B
               for p in ((0,) + q for q in permutations(range(1, n))))
def reduce(n, E):
    return [[0 if i == j else (1 if frozenset((i, j)) in E else 2) for j in range(n)] for i in range(n)]

yes = no = 0
for trial in range(150):
    n = random.randint(3, 7)
    E = {frozenset(e) for e in combinations(range(n), 2) if random.random() < 0.5}
    a, b = ham(n, E), tsp_at_most(reduce(n, E), n)
    assert a == b
    yes += a; no += not a
print(f"150 random graphs ({yes} with a Hamiltonian cycle, {no} without): the reduction is correct")

150 random graphs (42 with a Hamiltonian cycle, 108 without): the reduction is correct

NP-hard and NP-complete

A problem Y is NP-hard if every problem in NP reduces to it, and NP-complete if it is NP-hard and also in NP. NP-complete problems are the hardest problems in NP: if any one of them is in P, then \(\text{P} = \text{NP}\), and if any problem in NP is not in P, then no NP-complete problem is. It is not obvious that NP-complete problems exist at all, since NP-hardness requires a reduction from every problem in NP, including problems nobody has thought of yet. The Cook–Levin theorem (Cook 1971, Levin independently in 1973) shows that satisfiability is NP-complete, and lesson 9 sketches its proof. After that, proving a new problem NP-complete is much easier, because of transitivity: show it is in NP, and reduce any one known NP-complete problem to it.

If P is not equal to NP, the picture is richer than 'easy or NP-complete'. Ladner proved in 1975 that there would then be problems in NP that are neither in P nor NP-complete. Factoring and graph isomorphism are natural candidates. In 2015 László Babai announced a quasipolynomial-time algorithm for graph isomorphism, \(2^{O((\log n)^c)}\), which strongly suggests it is not NP-complete. Factoring has no known polynomial algorithm on classical computers, and the security of RSA rests on that, but it is in NP intersect co-NP and is not believed to be NP-complete.

Why this matters for practice

An NP-completeness proof changes what you do next. It tells you to stop looking for an algorithm that is exact, fast on every input and general, because finding one would resolve the most famous open problem in computer science. Instead you relax one of the three demands: accept approximate answers (lesson 10), accept algorithms that are fast on typical or structured inputs, or accept exponential time with a much smaller base or exponential only in a small parameter (lesson 12). Garey and Johnson's 1979 book Computers and Intractability catalogued hundreds of NP-complete problems for exactly this purpose, so that a practitioner could recognize a hard problem quickly.

Worked examples