Complexity theory & NP

1 · The complexity classes

Here's the meeting that ruins a sprint. A product manager drops a feature on your desk: "just build the scheduler that finds the optimal assignment of every task to every worker." It sounds routine — you've solved a hundred scheduling tickets. So you code, and your solver returns instantly on the demo data. Then it hits real data and runs for three days without finishing. You add threads, a faster machine, a cleverer loop — and it still crawls. What nobody told you is that this problem belongs to a family where no amount of cleverness is known to help. The complexity classes are the map that would have told you, on day one, which family you were in — so you'd stop hunting for a fast exact algorithm that almost certainly does not exist and reach for the right workaround instead.

Think of it as sorting problems into difficulty tiers, the way a climbing gym colour-codes routes. Some routes anyone can walk up (green). Some are genuinely hard to climb but, once someone's at the top, it's obvious they made it (blue). And some routes are so hard that if you could climb one of them freely, you could climb every hard route in the building. That last property — "crack one, crack them all" — is the strange and beautiful heart of this section, and it's what "NP-complete" means.

The single most common mistake is to hear "NP" and think "not polynomial" or "impossible." NP does not mean "not polynomial." It stands for nondeterministic polynomial, and the useful way to read it is "checkable in polynomial time." Plenty of problems in NP are easy; in fact every easy (P) problem is also in NP. Keep that straight and the rest of the lesson falls into place. With that framing, here are the four boxes precisely.

P is the set of decision problems solvable in polynomial time — the "tractable" problems, everything in this track so far. NP is the set of problems whose yes-answers can be verified in polynomial time given a short certificate (a proposed solution). Every problem in P is in NP. NP-complete problems are the hardest in NP: every NP problem reduces to them, so a polynomial algorithm for one would solve all of NP. NP-hard is "at least as hard as NP-complete" but not required to be in NP (it need not even be a decision problem — the optimisation TSP is NP-hard).

2 · NP = 'easy to verify' — a runnable verifier

You already know this asymmetry in your bones — from Sudoku. Handing someone a blank hard Sudoku and asking them to solve it can eat an afternoon of pencil-chewing. But hand them a completed grid and ask "is this a valid solution?" and they can check it in a minute: scan each row, each column, each box for duplicates, done. Solving is hard; checking is easy. That gap — between finding an answer and verifying one someone hands you — is not a quirk of Sudoku. It is the exact definition of the entire class NP, and it's worth slowing down on because it overturns the naive assumption that "hard to solve" and "hard to check" are the same thing.

Here's the vocabulary that makes it precise. The proposed answer someone hands you — the filled-in grid, the specific subset, the actual route — is called a certificate (or "witness"). A problem is in NP if there's a verifier: a polynomial-time procedure that takes your input plus a certificate and returns yes/no on whether the certificate really is a valid solution. Notice what the verifier is not allowed to do: it can't go find the certificate itself. It's a judge, not a detective. Someone (or some exponential search) has to produce the candidate; NP only promises the judging is fast.

The common trap is to conflate "we don't have a fast solver" with "verification must also be slow." Watch how independent those are: for subset-sum below, finding the right subset appears to need trying up to 2ⁿ combinations, but verifying a proposed subset is a single linear pass that adds the chosen numbers and compares to the target. A schoolchild could run the verifier; nobody knows a fast solver. When you can write the fast verifier but not the fast solver, you've found a genuine NP problem — and that's precisely the situation the whole lesson is built around. The lab makes both halves runnable so you can feel the asymmetry rather than take it on faith.

The defining feature of NP is not that problems are hard to solve but that solutions are easy to check. Subset-sum is the cleanest illustration: given a set of numbers and a target, does some subset sum to it? Finding that subset seems to need exponential search; verifying a proposed subset (the certificate) is a trivial linear-time addition. That asymmetry is NP.

import itertools

def verify_subset_sum(numbers, target, certificate):
    """A VERIFIER for subset-sum: given a proposed subset (the 'certificate'),
    check it in polynomial time. Fast verification is the essence of NP."""
    if not set(certificate).issubset(set(range(len(numbers)))):
        return False
    return sum(numbers[i] for i in certificate) == target

def solve_subset_sum_bruteforce(numbers, target):
    """FINDING the certificate is the hard part: 2^n subsets to try."""
    for r in range(len(numbers) + 1):
        for combo in itertools.combinations(range(len(numbers)), r):
            if sum(numbers[i] for i in combo) == target:
                return list(combo)
    return None

nums = [3, 34, 4, 12, 5, 2]
target = 9
cert = solve_subset_sum_bruteforce(nums, target)      # slow: explores 2^n
print("found subset indices :", cert)                 # e.g. [2, 4] -> 4+5=9
print("verifies?            :", verify_subset_sum(nums, target, cert))  # True
print("bogus cert verifies? :", verify_subset_sum(nums, target, [0, 1]))  # False

found subset indices : [2, 4]
verifies?            : True
bogus cert verifies? : False

3 · Polynomial-time reductions: 3-SAT → clique

Every engineer has quietly done a reduction without naming it. You need to sort a list of objects by a weird custom rule, so you write a comparison function and hand the whole thing to the language's built-in sort — you didn't reinvent sorting, you translated your problem into one that already had a solver. A reduction is exactly that move, promoted to a proof technique: rephrase problem A as an instance of problem B so that B's solver answers A. In everyday coding you use it to save effort. In complexity theory we flip it around and use it to spread bad news — to prove a new problem is hard.

The logic runs backwards from the way it first feels, so hold onto this analogy: reductions transfer difficulty like a chain of guarantees. Suppose you already know problem A is genuinely hard, and you show "if I could solve B quickly, I could solve A quickly" (by translating A into B in polynomial time). Then B must be at least as hard as A — because an easy B would hand you an easy A, which you know can't exist. So the arrow of a reduction points from the known-hard problem into the new one: reducing a known-hard A to your new B stamps B as hard. Beginners routinely get this direction backwards and "prove" the wrong thing, so say it out loud each time: hard problem → new problem means the new problem inherits the hardness.

This is why one problem — 3-SAT (is a boolean formula in three-literal clauses satisfiable?) — became the universal source of hardness. The Cook–Levin theorem proved 3-SAT is NP-complete, meaning every problem in NP can be translated into it. So the recipe for showing your new problem X is NP-hard is: reduce 3-SAT to X. That chains "every NP problem → 3-SAT → X," and X inherits the hardness of all of NP. (One honest footnote: this framework rests on P ≠ NP being true, which is still unproven — but the reduction machinery itself is airtight regardless of how that question resolves.) The lab performs the textbook 3-SAT → clique reduction and then checks that a satisfying assignment really does correspond to a clique, so you see the translation is faithful and not just asserted.

A reduction transforms problem A into problem B in polynomial time so that a solver for B solves A. Reductions are how we prove NP-completeness: since Cook-Levin showed 3-SAT is NP-complete, reducing 3-SAT to a new problem proves that problem is NP-hard too. The classic 3-SAT → clique reduction: make one vertex per literal-occurrence, connect vertices in different clauses that are not contradictory; the formula is satisfiable iff the graph has a clique of size k (one true literal per clause). The demo builds the graph and confirms the equivalence on a tiny instance.

import itertools

def three_sat_to_clique(clauses):
    """Reduce 3-SAT to CLIQUE (the textbook Karp reduction).

    Build a graph with one vertex per literal-occurrence. Connect two vertices
    if they are in DIFFERENT clauses AND are not contradictory (x and NOT x).
    A satisfying assignment exists  <=>  the graph has a clique of size k
    (k = number of clauses): pick one true literal per clause, all mutually
    consistent -> a clique.  literals are ints: 2 means x2, -2 means NOT x2."""
    verts = []                                # (clause_index, literal)
    for ci, clause in enumerate(clauses):
        for lit in clause:
            verts.append((ci, lit))
    edges = set()
    for a, b in itertools.combinations(range(len(verts)), 2):
        (ci, la), (cj, lb) = verts[a], verts[b]
        if ci != cj and la != -lb:            # different clause, not contradictory
            edges.add((a, b))
    return verts, edges

def has_clique(n, edges, k):
    """Brute-force clique check (itself exponential) — used only to CONFIRM the
    reduction is faithful on tiny instances."""
    adj = {i: set() for i in range(n)}
    for a, b in edges:
        adj[a].add(b); adj[b].add(a)
    for combo in itertools.combinations(range(n), k):
        if all(b in adj[a] for a, b in itertools.combinations(combo, 2)):
            return True
    return False

# (x1 OR x2 OR x3) AND (NOT x1 OR x2 OR x3) — satisfiable (e.g. x2=True)
clauses = [[1, 2, 3], [-1, 2, 3]]
verts, edges = three_sat_to_clique(clauses)
k = len(clauses)
print("literal-vertices :", len(verts))
print("has clique of size k=%d :" % k, has_clique(len(verts), edges, k))  # True

literal-vertices : 6
has clique of size k=2 : True

4 · The limits of computation — the halting problem

Every developer has stared at a spinning process and wondered: is it stuck in an infinite loop, or just slow? The obvious dream is a tool — call it will_it_finish(program, input) — that reads any code and tells you truthfully whether it will ever stop or run forever. It would be the ultimate linter: no more hung builds, no more "did the deploy freeze?" panic. The astonishing, provable fact of this section is that this tool cannot exist. Not "is hard to build," not "we haven't figured it out yet" — it is mathematically impossible, and Alan Turing proved it in 1936, before there were computers to run it on.

This is a different kind of limit from everything else in the lesson, and the distinction matters. NP-complete problems are hard because they're slow — give them enough centuries and a big enough machine and they'll finish. The halting problem is undecidable: no algorithm, with infinite time and infinite memory, can answer it correctly for every input. Time doesn't help. Faster hardware doesn't help. It's a wall, not a hill.

The proof is a self-reference trick — the same shape as the liar's paradox, "this sentence is false." Suppose the magic halts checker existed. Then you could build a spiteful little program that asks the checker about itself and then does the opposite: if the checker says "you'll halt," it deliberately loops forever; if the checker says "you'll loop," it immediately halts. Now ask the checker what that program does — and every answer it could give is instantly proven wrong by the program's own behaviour. The only escape from the contradiction is that the checker never existed. The common misconception to head off: this is not saying "some specific programs are hard to analyse." It's stronger — there's no general procedure that works for all of them. (Rice's theorem, in the note after the demo, generalises the damage to essentially every non-trivial question about what a program does.) The lab writes the paradox out as runnable-looking code so you can trace the contradiction line by line; it can't and doesn't implement a real oracle, because — that's the whole point — none can exist.

NP-hardness is about time. A deeper limit is decidability: some problems have no algorithm at all, at any cost. The halting problem — "does program P halt on input I?" — is the canonical undecidable problem. Turing’s diagonal argument: assume a halts oracle exists, build a program that halts iff the oracle says it loops, then feed it itself — a contradiction. So no such oracle can exist. This is conceptual; the demo sketches the paradox, it does not (and cannot) implement a real oracle.

def halting_paradox_sketch():
    """The halting problem is UNDECIDABLE: no program can decide, for every
    (program, input) pair, whether it halts. The classic diagonal argument,
    shown as a contradiction (this does NOT run a real 'halts' oracle)."""
    def halts(program, inp):
        raise NotImplementedError("assume this oracle exists, then derive absurdity")

    def paradox(program):
        if halts(program, program):
            while True:                       # if it halts, loop forever
                pass
        else:
            return                            # if it loops, halt

    # Now ask: does paradox(paradox) halt?
    #  - If halts(paradox, paradox) == True  -> paradox loops -> it does NOT halt.
    #  - If halts(paradox, paradox) == False -> paradox halts -> it DOES halt.
    # Both cases contradict the oracle. Therefore 'halts' cannot exist.
    return "No consistent 'halts' oracle can exist — halting is undecidable."

print(halting_paradox_sketch())

No consistent 'halts' oracle can exist — halting is undecidable.

5 · The classic NP-complete catalogue

The NP-complete problems almost never arrive wearing a name tag. No ticket in your backlog will say "please implement graph colouring." It'll say "make sure no two overlapping exams get scheduled in the same slot," or "assign each variable to a CPU register, but conflicting variables can't share one," or "plan the drone's delivery route so it visits every address and comes home." Those are all famous NP-complete problems in disguise — timetabling and register allocation are graph colouring; the drone route is the travelling salesman problem. The engineer who recognises the disguise saves a sprint; the one who doesn't promises a fast exact solution and then can't deliver it.

So think of this section as a face book for the usual suspects. You're not memorising proofs — you're training pattern recognition, the way a doctor learns to recognise a rash on sight rather than deriving it from first principles. Once you've seen that "pick a subset that hits a target" is subset-sum, "cover everything using as few sets as possible" is set cover, and "find a group where everyone is mutually connected" is clique, you'll start spotting them in feature requests before you write a line of code.

Two cautions keep this useful rather than paralysing. First, "NP-complete" is a worst-case, exact-solution label — it does not mean "unbuildable," and the very next section is the playbook for building anyway. Second, resist the urge to over-diagnose: not every hard-feeling problem is NP-complete, and many everyday tasks that smell like TSP (say, routing on a real road map with realistic constraints) have practical solvers that handle real instances fine. The skill is calibrated recognition — knowing when you've hit a genuine member of this family so you switch strategies deliberately, not reflexively. The table below is your starting reference: the canonical question each problem asks, and the real-world clothing it tends to show up in.

You do not need to memorise proofs, but you must recognise these when they appear in disguise — a scheduling ticket that is secretly graph colouring, a routing feature that is secretly TSP. Spotting the pattern saves you from promising a fast exact solution you cannot deliver.

6 · The engineer's playbook: approximation & heuristics

Here's the plot twist that makes this whole lesson practical rather than depressing. Your GPS routes millions of deliveries a day. Airlines schedule crews. Compilers allocate registers. Chip designers pack billions of transistors. Every one of those is a certified NP-hard problem — and yet all of them ship, work well, and run fast. If NP-hardness meant "impossible," none of that software would exist. The resolution is that NP-hardness is a claim about the worst case on adversarial input, and the real world almost never hands you the worst case. The professional move isn't to solve the impossible; it's to notice you don't actually need to.

The mental unlock is to stop demanding "the exact optimal answer, guaranteed, on any input." Loosen just one of those three demands and the problem cracks open. Think of it like planning a road trip: you don't need the provably shortest route that would take a supercomputer a week to compute — you need a good route, right now. Willing to trade a little quality for enormous speed is what turns an intractable problem into a shipped feature, and there are four distinct levers for making that trade, each with a different guarantee.

Know the four so you can pick deliberately. (1) Exact on small n: if your input is genuinely tiny, brute force or dynamic programming is fine — an exponential algorithm on n=12 finishes instantly. (2) Approximation algorithms: these come with a provable quality bound, like "guaranteed within 2× of optimal" — you sacrifice optimality but keep a mathematical promise. (3) Heuristics (greedy, local search, simulated annealing): fast and usually good, but with no guarantee — they can occasionally be bad, and you accept that risk for speed. (4) Mature solvers: modern SAT, ILP, and CP solvers routinely crush "hard" instances with millions of variables, precisely because real inputs aren't adversarial — and the biggest mistake here is hand-rolling your own when a battle-tested solver would do far better. The trap to avoid runs the other way from the earlier sections: don't let "NP-hard" scare you into not building. The two labs below make the trade concrete — first an exact TSP against a greedy heuristic (fast, no guarantee), then a vertex-cover algorithm that is provably within 2× of optimal (slower promise, ironclad bound).

NP-completeness is a statement about worst-case exact solutions on arbitrary inputs. Real work rarely needs that. The practical responses: (1) exact on small n — brute force or DP is fine when n is tiny or the number is small (pseudo-polynomial knapsack); (2) approximation algorithms with a provable ratio (2-approx vertex cover, ln n set cover); (3) heuristics (greedy, local search, simulated annealing) that are fast and usually good but carry no guarantee; (4) solvers — modern SAT/ILP solvers crush huge "hard" instances because real inputs are not adversarial. The first demo compares an exact TSP to a greedy heuristic; the second gives a guaranteed 2-approximation.

import itertools, random

def tsp_bruteforce(dist):
    """Exact travelling-salesman (return to start). O(n!) — only tiny n."""
    n = len(dist)
    best, best_tour = float("inf"), None
    for perm in itertools.permutations(range(1, n)):
        tour = (0,) + perm + (0,)
        cost = sum(dist[tour[i]][tour[i + 1]] for i in range(n))
        if cost < best:
            best, best_tour = cost, tour
    return best, best_tour

def tsp_nearest_neighbour(dist):
    """A greedy HEURISTIC: always go to the nearest unvisited city. O(n^2).
    Fast but NOT optimal — a bounded, practical answer instead of an exact one."""
    n = len(dist)
    unvisited = set(range(1, n))
    tour, cur, cost = [0], 0, 0
    while unvisited:
        nxt = min(unvisited, key=lambda c: dist[cur][c])
        cost += dist[cur][nxt]
        cur = nxt; tour.append(cur); unvisited.discard(cur)
    cost += dist[cur][0]; tour.append(0)
    return cost, tour

random.seed(7)
n = 8
pts = [(random.random(), random.random()) for _ in range(n)]
dist = [[((a[0]-b[0])**2 + (a[1]-b[1])**2) ** 0.5 for b in pts] for a in pts]
exact, _ = tsp_bruteforce(dist)
approx, _ = tsp_nearest_neighbour(dist)
print("exact  cost : %.3f" % exact)
print("greedy cost : %.3f" % approx)
print("greedy within %.1f%% of optimal" % (100 * (approx - exact) / exact))

exact  cost : 2.320
greedy cost : 2.389
greedy within 3.0% of optimal

def vertex_cover_2approx(edges):
    """2-approximation for minimum vertex cover (NP-hard to solve exactly).
    Repeatedly pick any uncovered edge and take BOTH endpoints. The result is
    at most 2x the optimum — a provable guarantee, not just a hope."""
    cover = set()
    remaining = set(map(tuple, (map(lambda e: tuple(sorted(e)), edges))))
    while remaining:
        u, v = next(iter(remaining))
        cover.add(u); cover.add(v)
        remaining = {(a, b) for (a, b) in remaining if a not in (u, v) and b not in (u, v)}
    return cover

edges = [(0, 1), (1, 2), (2, 3), (3, 0), (1, 3)]
cover = vertex_cover_2approx(edges)
covered = all(a in cover or b in cover for a, b in edges)
print("cover      :", sorted(cover))
print("covers all edges :", covered)
print("size <= 2x optimal (guaranteed) :", True)

cover      : [0, 1, 2, 3]
covers all edges : True
size <= 2x optimal (guaranteed) : True

def verify_hamiltonian_path(n, edges, order):
    """VERIFY a proposed Hamiltonian path (visits every vertex exactly once).
    Verification is polynomial; finding one is NP-complete."""
    if sorted(order) != list(range(n)):
        return False                          # must be a permutation of all vertices
    edge_set = {tuple(sorted(e)) for e in edges}
    return all(tuple(sorted((order[i], order[i + 1]))) in edge_set
               for i in range(n - 1))

edges = [(0, 1), (1, 2), (2, 3), (0, 3)]
print("0-1-2-3 valid? :", verify_hamiltonian_path(4, edges, [0, 1, 2, 3]))  # True
print("0-2-1-3 valid? :", verify_hamiltonian_path(4, edges, [0, 2, 1, 3]))  # False

import itertools

def brute_force_sat(clauses, n_vars):
    """Decide CNF-SAT by trying all 2^n truth assignments. Exponential, but the
    ground truth against which heuristics are measured."""
    for bits in itertools.product([False, True], repeat=n_vars):
        assign = {i + 1: bits[i] for i in range(n_vars)}
        def lit_true(lit):
            return assign[abs(lit)] if lit > 0 else not assign[abs(lit)]
        if all(any(lit_true(l) for l in clause) for clause in clauses):
            return assign
    return None

clauses = [[1, 2], [-1, 2], [-2, 3]]
sol = brute_force_sat(clauses, 3)
print("satisfying assignment :", sol)          # e.g. {1:False,2:True,3:True}
print("unsat example :", brute_force_sat([[1], [-1]], 1))  # None

def independent_set_to_clique(n, edges):
    """Reduce INDEPENDENT SET to CLIQUE by complementing the graph:
    an independent set in G is exactly a clique in the complement of G."""
    present = {tuple(sorted(e)) for e in edges}
    complement = [(a, b) for a in range(n) for b in range(a + 1, n)
                  if (a, b) not in present]
    return complement

import itertools
def has_clique(n, edges, k):
    adj = {i: set() for i in range(n)}
    for a, b in edges:
        adj[a].add(b); adj[b].add(a)
    return any(all(b in adj[a] for a, b in itertools.combinations(c, 2))
               for c in itertools.combinations(range(n), k))

# path 0-1-2-3: {0,2} and {1,3} are independent sets of size 2
edges = [(0, 1), (1, 2), (2, 3)]
comp = independent_set_to_clique(4, edges)
print("independent set size 2 <=> clique size 2 in complement :",
      has_clique(4, comp, 2))                   # True

def greedy_set_cover(universe, subsets):
    """Greedy approximation for SET COVER (NP-hard). Repeatedly take the subset
    covering the most still-uncovered elements. Guarantee: at most H(n) ~ ln n
    times the optimal number of subsets."""
    universe = set(universe)
    uncovered = set(universe)
    chosen = []
    sets = {k: set(v) for k, v in subsets.items()}
    while uncovered:
        best = max(sets, key=lambda k: len(sets[k] & uncovered))
        if not (sets[best] & uncovered):
            break                               # cannot cover the rest
        chosen.append(best)
        uncovered -= sets[best]
    return chosen, not uncovered

universe = [1, 2, 3, 4, 5]
subsets = {"A": [1, 2, 3], "B": [2, 4], "C": [3, 4], "D": [4, 5]}
chosen, ok = greedy_set_cover(universe, subsets)
print("chosen subsets :", chosen)
print("fully covered  :", ok)

import random

def maxcut_local_search(n, edges, seed=0):
    """MAX-CUT is NP-hard. Local search: start random, flip any vertex that
    increases the cut, repeat until stable. A simple 0.5-approximation-quality
    heuristic (random assignment alone already expects half the edges cut)."""
    rnd = random.Random(seed)
    side = [rnd.randint(0, 1) for _ in range(n)]
    adj = {i: [] for i in range(n)}
    for a, b in edges:
        adj[a].append(b); adj[b].append(a)

    def cut_value():
        return sum(1 for a, b in edges if side[a] != side[b])

    improved = True
    while improved:
        improved = False
        for v in range(n):
            same = sum(1 for w in adj[v] if side[w] == side[v])
            diff = len(adj[v]) - same
            if same > diff:                     # flipping v cuts more edges
                side[v] ^= 1
                improved = True
    return cut_value(), side

edges = [(0, 1), (1, 2), (2, 3), (3, 0), (0, 2)]
value, side = maxcut_local_search(5 if False else 4, edges)
print("cut value :", value)
print("sides     :", side)

import itertools, random, time

def knapsack_exact(items, cap):
    """0/1 knapsack via DP: O(n * cap) — pseudo-polynomial (polynomial in the
    NUMBER cap, exponential in its bit-length). The optimum baseline."""
    n = len(items)
    dp = [0] * (cap + 1)
    for w, v in items:
        for c in range(cap, w - 1, -1):
            dp[c] = max(dp[c], dp[c - w] + v)
    return dp[cap]

def knapsack_greedy(items, cap):
    """Greedy by value density (v/w). Fast heuristic, NOT optimal for 0/1."""
    order = sorted(items, key=lambda it: it[1] / it[0], reverse=True)
    total = w = 0
    for wi, vi in order:
        if w + wi <= cap:
            w += wi; total += vi
    return total

random.seed(1)
items = [(random.randint(1, 10), random.randint(1, 20)) for _ in range(15)]
cap = 30
opt = knapsack_exact(items, cap)
approx = knapsack_greedy(items, cap)
print("exact  value :", opt)
print("greedy value :", approx)
print("greedy ratio : %.2f" % (approx / opt))
# Honest note: for 0/1 knapsack the greedy density heuristic has NO constant
# approximation guarantee (unlike fractional knapsack). A true FPTAS exists.