Chapter 11 introduced Big-O informally; complexity theory makes it rigorous and asks a sharper question than "how fast": which decidable problems have a fast algorithm, and which don't? Define P (polynomial time) as the class of decision problems solvable by an algorithm whose running time is O(nᵏ) for some constant k — considered "efficiently solvable." Define NP (nondeterministic polynomial time) as the class of decision problems whose proposed solutions can be verified in polynomial time, even when no fast way to find one is known.

Every problem in P is also in NP — if you can solve it fast, you can certainly verify a solution fast. Whether the reverse holds — whether P = NP — is the most famous open problem in computer science, one of the seven Clay Millennium Prize problems. A problem is NP-complete if it is in NP and every other NP problem can be transformed into it in polynomial time (a reduction), making NP-complete problems the "hardest in NP." Cook and Levin proved in 1971 that Boolean satisfiability (SAT) is NP-complete; thousands of practical problems — scheduling, packing, routing — have since been shown NP-complete by reduction to SAT or to each other.

The gap between "verify" and "solve" is the crux. Given a proposed route for the travelling salesman, checking its total distance is fast — a single pass, O(n). But finding the shortest such route among all possible orderings appears to require checking an exponential number of candidates — nobody has found a fundamentally faster way for the general case, despite fifty years of trying by the best minds in the field. Most computer scientists believe P ≠ NP — that verifying is genuinely easier than solving — but no proof exists either way.

This is not merely academic. Modern cryptography (Chapter 21) depends on certain problems, like factoring large numbers, being hard to solve but the resulting keys easy to verify. If someone proved P = NP and produced a practical fast algorithm, most of today's encryption would become breakable overnight.

The subset-sum problem — does some subset of a list of numbers add up to exactly a target? — is NP-complete. We show the gap directly: checking a candidate answer is fast (linear), while searching for one by brute force is exponential.

from itertools import combinations
import time

def verify_subset_sum(numbers, target, candidate_subset):    # O(n): the "NP" verifier
    return sum(candidate_subset) == target and all(x in numbers for x in candidate_subset)

def solve_subset_sum_bruteforce(numbers, target):             # O(2^n): the "solver"
    n = len(numbers)
    for size in range(n + 1):                      # try every possible subset size
        for combo in combinations(numbers, size):  # try every subset of that size
            if sum(combo) == target:
                return combo
    return None

numbers = [3, 34, 4, 12, 5, 2]
target = 9

# Verifying a GIVEN answer is instant, regardless of how it was found:
candidate = (4, 5)
print("verify:", verify_subset_sum(numbers, target, candidate))   # True, O(n) work

# Finding an answer from scratch costs exponentially more as n grows:
start = time.time()
found = solve_subset_sum_bruteforce(numbers, target)
print("solved:", found, "in", round(time.time() - start, 6), "s")

# Double the list length and brute force roughly SQUARES the number of subsets checked
# (2^12 vs 2^6 = 64x more work) -- this is what "exponential" costs in practice.

Verification touches each candidate once — cheap and predictable. The brute-force solver enumerates all 2ⁿ subsets in the worst case; no known algorithm avoids this exponential blow-up for subset-sum in general, exactly the signature of an NP-complete problem.