P, NP and polynomial-time reductions

Every problem so far has had an efficient algorithm. The rest of the course turns to problems that, as far as anyone knows, do not. Recognizing such problems is an essential engineering skill, because the alternative is spending weeks hunting for a fast exact algorithm that almost certainly does not exist. This lesson defines the classes P and NP, introduces polynomial-time reductions, the tool that compares the difficulty of problems, and explains what the famous P versus NP question asks. Lesson 11 then proves that a family of important problems, the NP-complete problems, are all equally hard, and lesson 12 explains what engineers do when they meet one.

The subject arrives at Northway through gateway placement. The new contract covers a corridor where every counter must be within radio range of at least one solar gateway, gateways can only be mounted at certain poles, and each gateway costs about 4,000 dollars installed. Dana asks Jonah for the cheapest set of poles. He writes a brute-force search, it finishes instantly for the 12 candidate poles in the pilot area, and then it runs all weekend without finishing for the 70 poles in the full corridor. That experience, a problem whose obvious algorithm explodes and whose clever algorithm refuses to appear, is what this lesson is about.

Decision problems

The theory is cleanest for decision problems, whose answer is yes or no. Optimization problems are turned into decision problems by adding a threshold. Instead of 'find the fewest gateways that cover every counter', ask 'can every counter be covered with at most k gateways?' The two versions are equally hard up to a polynomial factor: if the decision version can be solved quickly, binary search over k finds the optimum value with about log₂ n calls, and a few more calls recover the actual set. Conversely, solving the optimization version answers every decision question at once.

An instance of a decision problem is encoded as a string, and the problem is the set of strings whose answer is yes. Input size is the length of that string, which for graphs is about the number of vertices plus edges and for numbers is their length in bits, as lesson 1 insisted.

The class P

P is the class of decision problems that can be solved by an algorithm whose worst-case running time is polynomial in the input size. Everything in lessons 2 to 9 is in P: interval scheduling, shortest paths, maximum flow, matching, edit distance, and many more. Linear programming, primality testing (proved in P in 2002 by Agrawal, Kayal and Saxena) and two-satisfiability are less obvious members. P is the theoretical formalization of 'efficiently solvable', with the caveats lesson 1 discussed.

The class NP

NP is the class of decision problems for which a yes answer can be verified in polynomial time, given a suitable certificate. For gateway placement, the certificate is a list of at most k poles; checking that every counter is within range of one of them takes time polynomial in the number of counters and poles. Finding such a list may be very hard, but checking a proposed one is easy. Formally, a problem is in NP if there is a polynomial-time verifier V and a polynomial bound on certificate length such that an instance x is a yes instance exactly when some certificate c makes V(x, c) accept.

The name stands for nondeterministic polynomial time, from an equivalent definition in which a machine may guess the certificate. It does not stand for 'not polynomial'. Every problem in P is in NP, because a polynomial algorithm can verify by ignoring the certificate and solving the instance. The open question is whether the reverse holds.

NP is not symmetric. Verifying that no set of k gateways suffices seems to require examining all of them; there is no obvious short certificate for a no answer. Problems whose no answers have short certificates form the class co-NP. Whether NP equals co-NP is another open question, closely tied to P versus NP.

Polynomial-time reductions

A reduction converts instances of one problem into instances of another so that the answer is preserved. Problem A reduces to problem B in polynomial time, written A ≤_p B, if there is a polynomial-time function f that maps every instance x of A to an instance f(x) of B, with x a yes instance of A exactly when f(x) is a yes instance of B. If B can be solved in polynomial time, so can A: transform the instance and solve it as B. Read the other way, if A is hard, B must be at least as hard.

Reductions have already appeared in this course. Lesson 6 reduced bipartite matching to maximum flow, and lesson 7 reduced difference constraints to shortest paths. Those reductions were used to solve problems. In complexity theory the same tool is used in reverse, to prove that problems are hard. The direction is the most common source of confusion: to show B is hard, reduce a known hard problem A to B, not B to A. Reducing B to a hard problem only shows that B is no harder than that problem, which says nothing useful.

Three reductions between classic problems

Independent set asks whether a graph has k vertices with no edge between any two of them. Vertex cover asks whether k vertices touch every edge. They are two views of the same structure: a set S is independent exactly when its complement V − S is a vertex cover, because an edge with both ends outside the cover would have both ends in S. So a graph with n vertices has an independent set of size k exactly when it has a vertex cover of size n − k. The reduction maps (G, k) to (G, n − k) and takes linear time, so the two problems are equally hard.

Clique asks whether a graph has k vertices that are all pairwise adjacent. A set is a clique in G exactly when it is independent in the complement graph, which has an edge wherever G does not. Building the complement takes O(n²) time, so clique and independent set reduce to each other.

Set cover generalizes vertex cover. Given a collection of subsets of a universe and a number k, can k subsets cover the whole universe? Vertex cover reduces to set cover by making the universe the edges and giving each vertex the set of edges it touches. Jonah's gateway problem is a set cover problem: the universe is the counters, and each candidate pole contributes the set of counters within its radio range. The reduction shows that gateway placement is at least as hard as vertex cover, which lesson 11 shows is NP-complete.

# Reductions in code: independent set <-> vertex cover, and vertex cover -> set cover
from itertools import combinations

edges = [(1, 2), (1, 3), (2, 3), (3, 4), (4, 5), (2, 5)]
V = sorted({v for e in edges for v in e})

def is_cover(S):
    return all(u in S or v in S for u, v in edges)

def is_independent(S):
    return all(not (u in S and v in S) for u, v in edges)

def brute(pred, k):
    return any(pred(set(c)) for c in combinations(V, k))

for k in range(1, len(V) + 1):
    print(f"independent set of size {k}: {brute(is_independent, k)!s:5s}  "
          f"vertex cover of size {len(V) - k}: {brute(is_cover, len(V) - k)}")

# vertex cover as set cover: universe = edges, each vertex covers its incident edges
universe = set(edges)
sets = {v: {e for e in edges if v in e} for v in V}
k = 3
found = [c for c in combinations(V, k) if set().union(*(sets[v] for v in c)) == universe]
print("set cover with 3 sets:", found[0] if found else None, "is also a vertex cover:", is_cover(set(found[0])))

independent set of size 1: True   vertex cover of size 4: True
independent set of size 2: True   vertex cover of size 3: True
independent set of size 3: False  vertex cover of size 2: False
independent set of size 4: False  vertex cover of size 1: False
independent set of size 5: False  vertex cover of size 0: False
set cover with 3 sets: (1, 2, 4) is also a vertex cover: True

NP-hard and NP-complete

A problem B is NP-hard if every problem in NP reduces to it in polynomial time. It is NP-complete if it is NP-hard and also in NP. NP-complete problems are the hardest problems in NP: a polynomial-time algorithm for any one of them would give polynomial-time algorithms for every problem in NP, through the chain of reductions. Thousands of problems from every field of engineering and science are now known to be NP-complete, and none has a known polynomial algorithm.

Proving that a new problem B is NP-complete takes two steps. Show that B is in NP by describing a certificate and a polynomial verifier. Then choose a known NP-complete problem A and give a polynomial-time reduction from A to B, proving both directions: yes instances of A become yes instances of B, and yes instances of B came from yes instances of A. Because reductions compose, this shows every NP problem reduces to B. Lesson 11 starts the chain with the Cook-Levin theorem, which proves directly that satisfiability is NP-complete, and builds the rest from it.

The P versus NP question

The central open question is whether P equals NP: whether every problem whose solutions can be checked quickly can also be solved quickly. Most researchers believe P ≠ NP, partly because decades of effort by very capable people have failed to find a polynomial algorithm for any NP-complete problem, and partly because a world in which finding were as easy as checking would be strange: mathematical proofs, which are easy to check, would be easy to find. The Clay Mathematics Institute has offered a million-dollar prize since 2000 for a proof either way.

The question has practical stakes. Modern cryptography assumes that certain problems in NP, such as inverting a well-designed hash function, are hard; if P = NP with a practical algorithm, much of it would collapse. On the other hand, scheduling, routing, chip layout and protein design would become easy. For an engineer, an NP-completeness proof is a strong signal to stop searching for a fast exact algorithm and to choose one of the strategies in lesson 12.

Beyond NP

Some problems are harder still. PSPACE contains problems solvable with polynomial memory but perhaps exponential time, such as deciding who wins certain generalized board games. EXPTIME problems provably need exponential time. Some problems are undecidable: no algorithm can solve them at all. The halting problem, deciding whether an arbitrary program halts on a given input, is the classic example, and Alan Turing proved its undecidability in 1936 by a diagonal argument. The halting problem is NP-hard, since anything reduces to it, but not in NP, which is why the NP-hard region in the figure extends outside NP. CMPUT-474 Theory of Computation develops these ideas fully.