Capstone: randomness, approximation, quantum computing and complexity in practice

The previous lessons drew a map: regular and context-free languages, decidable and undecidable problems, and the classes P, NP and PSPACE. This final lesson visits the regions of complexity theory that matter most in practice and in current research. Randomness gives algorithms that are simpler and faster, at the cost of a tiny probability of error, and raises the question of whether randomness is ever truly necessary. Approximation asks how close to optimal we can get efficiently when exact answers are NP-hard, and the PCP theorem shows that for some problems even approximation is hard. Parameterized and fine-grained complexity refine the coarse picture of P versus NP. Quantum computing challenges the extended Church–Turing thesis. And SAT solvers show that 'NP-complete' does not mean 'hopeless in practice'.

Randomized computation

A probabilistic Turing machine can flip fair coins. Different error conventions give different classes. BPP (bounded-error probabilistic polynomial time) contains languages decided in polynomial time with error probability at most 1/3 on every input. RP allows only one-sided error: on yes-instances the machine accepts with probability at least 1/2, and on no-instances it never accepts. ZPP allows no error at all but only bounds the expected running time; equivalently \(\text{ZPP} = \text{RP} \cap \text{coRP}\). The constants are arbitrary, because error can be driven down exponentially by repetition: running a BPP algorithm k times and taking the majority answer reduces the error to \(2^{-\Omega(k)}\) by the Chernoff bound. After a few dozen repetitions the chance of error is smaller than the chance of a hardware fault.

The classic example is primality testing. The Miller–Rabin test, from the 1970s, picks a random base a and checks a condition that every prime satisfies and that, for a composite n, at most a quarter of the bases satisfy. One round therefore detects compositeness with probability at least 3/4, and 20 rounds leave an error probability below \(4^{-20}\), about \(10^{-12}\). It is simple, fast and used in essentially every cryptographic library. The program below runs it on Carmichael numbers such as 561, which fool the simpler Fermat test, and measures how many bases actually lie: usually far fewer than the worst-case bound of a quarter, though some composites, such as 8,911, come close to it. In 2002 Agrawal, Kayal and Saxena found a deterministic polynomial-time primality test, putting PRIMES in P, but Miller–Rabin remains the method of choice because it is much faster.

# Miller-Rabin: a randomized primality test with one-sided error (the idea behind RP and BPP).
# A composite n survives one random round with probability at most 1/4; primes always pass.
import random
random.seed(474)

def mr_round(n, a):
    d, r = n - 1, 0
    while d % 2 == 0: d //= 2; r += 1
    x = pow(a, d, n)
    if x in (1, n - 1): return True
    for _ in range(r - 1):
        x = x * x % n
        if x == n - 1: return True
    return False

def is_probable_prime(n, rounds=20):
    if n < 4: return n in (2, 3)
    if n % 2 == 0: return False
    return all(mr_round(n, random.randrange(2, n - 1)) for _ in range(rounds))

for n in [561, 1105, 7919, 2 ** 61 - 1, 2 ** 61 + 1, 1_000_000_007 * 998_244_353]:
    print(f"{n:>22d}: {'probably prime' if is_probable_prime(n) else 'composite'}")
# how often does one round wrongly pass a composite? (strong liars)
for n in [561, 1105, 8911, 25326001]:
    liars = sum(mr_round(n, a) for a in range(2, n - 1)) if n < 10 ** 5 else None
    if liars is not None:
        print(f"n = {n}: {liars} of {n - 3} bases pass ({liars / (n - 3):.4f}; the bound is 0.25)")
    else:
        sample = [random.randrange(2, n - 1) for _ in range(20000)]
        p = sum(mr_round(n, a) for a in sample) / len(sample)
        print(f"n = {n}: sampled pass rate {p:.4f} (the bound is 0.25)")

                   561: composite
                  1105: composite
                  7919: probably prime
   2305843009213693951: probably prime
   2305843009213693953: composite
    998244359987710471: composite
n = 561: 8 of 558 bases pass (0.0143; the bound is 0.25)
n = 1105: 28 of 1102 bases pass (0.0254; the bound is 0.25)
n = 8911: 1780 of 8908 bases pass (0.1998; the bound is 0.25)
n = 25326001: sampled pass rate 0.1017 (the bound is 0.25)

Is randomness necessary for efficient computation? The prevailing belief is no: \(\text{P} = \text{BPP}\). The evidence is the hardness versus randomness paradigm. Impagliazzo and Wigderson proved in 1997 that if some problem solvable in exponential time requires exponential-size circuits, a plausible assumption, then every BPP algorithm can be derandomized with only polynomial slowdown, by replacing true random bits with the output of a pseudorandom generator built from the hard problem. Primality is a success story of derandomization in practice. A notable problem still without a known deterministic polynomial algorithm is polynomial identity testing: deciding whether an arithmetic circuit computes the zero polynomial, which has a simple randomized algorithm based on evaluating at random points (the Schwartz–Zippel lemma).

Approximation and the PCP theorem

For an NP-hard optimization problem, an α-approximation algorithm runs in polynomial time and always returns a solution within a factor α of optimal. Approximability varies enormously across problems. VERTEX-COVER has a simple 2-approximation: repeatedly pick an uncovered edge and add both its endpoints. The chosen edges form a matching, any cover needs one endpoint of each, so the result is at most twice optimal. The program below compares it with the exact optimum on random graphs. The KNAPSACK problem has a fully polynomial-time approximation scheme, getting within \(1 + \epsilon\) in time polynomial in n and \(1/\epsilon\), by rounding values and using the pseudo-polynomial dynamic program from lesson 10. The travelling salesperson problem in metric spaces has a 1.5-approximation, Christofides' algorithm from 1976, improved by a tiny constant only in 2020 by Karlin, Klein and Oveis Gharan; for general TSP with arbitrary distances no constant-factor approximation exists unless \(\text{P} = \text{NP}\).

# Approximation: the matching-based 2-approximation for VERTEX-COVER versus the optimum.
import random
from itertools import combinations
random.seed(474)

def two_approx(edges):
    cover = set()
    for u, v in edges:                      # take both ends of any uncovered edge
        if u not in cover and v not in cover:
            cover |= {u, v}
    return cover

def optimum(n, edges):
    for k in range(n + 1):
        for S in combinations(range(n), k):
            s = set(S)
            if all(u in s or v in s for u, v in edges): return k

print(" n  edges  2-approx  optimum  ratio")
worst = 0
for trial in range(8):
    n = 14
    edges = [(u, v) for u, v in combinations(range(n), 2) if random.random() < 0.2]
    a, o = len(two_approx(edges)), optimum(n, edges)
    worst = max(worst, a / o)
    print(f"{n:2d}  {len(edges):5d}  {a:8d}  {o:7d}  {a / o:.2f}")
print("worst ratio seen:", round(worst, 2), "(guaranteed never above 2)")

 n  edges  2-approx  optimum  ratio
14     23        10        7  1.43
14     15        12        7  1.71
14     17        10        7  1.43
14     18        12        7  1.71
14     21        10        7  1.43
14     15         8        5  1.60
14     21        12        7  1.71
14     18        12        7  1.71
worst ratio seen: 1.71 (guaranteed never above 2)

Why can some problems not be approximated? The deepest answer is the PCP theorem (Arora, Lund, Motwani, Sudan and Szegedy; Arora and Safra; 1992). It says that every language in NP has probabilistically checkable proofs: certificates, written in a special error-correcting format, that a verifier can check by reading only a constant number of randomly chosen bits, accepting correct proofs always and rejecting any claimed proof of a false statement with probability at least 1/2. Equivalently, there is a constant \(\epsilon > 0\) such that it is NP-hard to distinguish satisfiable 3SAT formulas from those in which at most a \(1 - \epsilon\) fraction of clauses can be satisfied. Håstad sharpened this in 2001: a random assignment satisfies 7/8 of the clauses of a 3SAT formula in expectation, and doing any better than \(7/8 + \epsilon\) is NP-hard. Irit Dinur gave a combinatorial proof of the PCP theorem in 2007. The Unique Games Conjecture of Khot (2002), still open, would pin down the exact approximability of many more problems, including vertex cover, for which it would make 2 the best possible factor.

Parameterized and fine-grained complexity

NP-completeness measures difficulty by input size alone. Parameterized complexity, developed by Downey and Fellows in the 1990s, adds a second parameter k, such as the size of the solution sought. A problem is fixed-parameter tractable (FPT) if it can be solved in time \(f(k) \cdot n^{O(1)}\) for some function f, so that the exponential part depends only on k. VERTEX-COVER is FPT: an edge's endpoints cannot both be left out, so branching on them gives a search tree with at most \(2^k\) leaves; improved algorithms run in about \(1.27^k \cdot n\) time. The program below finds covers of size 8 in graphs with ten thousand vertices instantly. By contrast CLIQUE parameterized by k is complete for the class W[1] and is believed not to be FPT. Parameterized algorithms explain why some NP-hard problems are routinely solved when the relevant parameter, such as tree width, is small.

# Parameterized complexity: VERTEX-COVER with parameter k by bounded search.
# Some endpoint of any edge must be in the cover, so branch on the two endpoints:
# at most 2^k branches, each polynomial. Fast whenever k is small, however large n is.
import random
random.seed(474)

def vc_branch(edges, k, stats):
    stats[0] += 1
    if not edges: return True
    if k == 0: return False
    u, v = edges[0]
    return (vc_branch([e for e in edges if u not in e], k - 1, stats) or
            vc_branch([e for e in edges if v not in e], k - 1, stats))

for n in (100, 1000, 10000):
    # a graph with a planted cover of size 8: every edge touches one of 8 hub vertices
    hubs = list(range(8))
    edges = [(random.choice(hubs), random.randrange(8, n)) for _ in range(3 * n)]
    for k in (7, 8):
        st = [0]
        ok = vc_branch(edges, k, st)
        print(f"n = {n:5d}, {len(edges):5d} edges, k = {k}: cover exists {ok!s:5}  search nodes {st[0]}")

n =   100,   300 edges, k = 7: cover exists False  search nodes 255
n =   100,   300 edges, k = 8: cover exists True   search nodes 9
n =  1000,  3000 edges, k = 7: cover exists False  search nodes 255
n =  1000,  3000 edges, k = 8: cover exists True   search nodes 9
n = 10000, 30000 edges, k = 7: cover exists False  search nodes 255
n = 10000, 30000 edges, k = 8: cover exists True   search nodes 9

Fine-grained complexity asks about exact exponents inside P. Many problems have had the same quadratic or cubic algorithm for decades, such as edit distance (\(O(n^2)\)), all-pairs shortest paths (\(O(n^3)\)) and 3SUM (\(O(n^2)\)). Fine-grained reductions tie them to a few hypotheses. The Strong Exponential Time Hypothesis (SETH, Impagliazzo and Paturi, 1999) states that for every \(\epsilon > 0\) there is a k such that k-SAT cannot be solved in \(O(2^{(1-\epsilon)n})\) time. Backurs and Indyk showed in 2015 that an edit-distance algorithm running in \(O(n^{2-\delta})\) time for any \(\delta > 0\) would refute SETH. Such conditional lower bounds, now known for many problems in bioinformatics, string processing and graph algorithms, explain why practitioners settle for heuristics or approximations on large inputs.

Quantum computation

A quantum computer manipulates qubits, whose joint state is a vector of complex amplitudes over all \(2^n\) bit strings, evolved by unitary operations and observed by measurement, which yields each string with probability equal to the squared magnitude of its amplitude. BQP is the class of problems a quantum computer solves in polynomial time with bounded error. It is known that \(\text{BPP} \subseteq \text{BQP} \subseteq \text{PSPACE}\). Shor's algorithm (1994) factors integers and computes discrete logarithms in polynomial time, problems believed not to be in BPP, which is the strongest evidence that quantum computers violate the extended Church–Turing thesis. Grover's algorithm (1996) searches N unstructured items with about \(\sqrt{N}\) queries instead of N, a quadratic speedup that is provably optimal; it does not make NP-complete problems easy, and BQP is not believed to contain NP. The program below simulates Grover's iteration classically for small N.

# Classical simulation of Grover's search on 2^n items: about (pi/4) sqrt(N) iterations
# make the marked item likely, compared with N/2 expected classical guesses.
import math
for n in (4, 6, 8, 10, 12):
    N = 2 ** n
    amp = [1 / math.sqrt(N)] * N
    marked = N // 3
    k = int(math.pi / 4 * math.sqrt(N))
    for _ in range(k):
        amp[marked] = -amp[marked]                  # oracle: flip the sign of the marked item
        mean = sum(amp) / N
        amp = [2 * mean - a for a in amp]           # diffusion: reflect about the mean
    print(f"N = {N:5d}: {k:3d} Grover iterations, P(marked) = {amp[marked] ** 2:.4f};  classical expected tries {N // 2}")

N =    16:   3 Grover iterations, P(marked) = 0.9613;  classical expected tries 8
N =    64:   6 Grover iterations, P(marked) = 0.9966;  classical expected tries 32
N =   256:  12 Grover iterations, P(marked) = 0.9999;  classical expected tries 128
N =  1024:  25 Grover iterations, P(marked) = 0.9995;  classical expected tries 512
N =  4096:  50 Grover iterations, P(marked) = 0.9999;  classical expected tries 2048

As of October 2026 no quantum computer has factored a number anywhere near cryptographic size, but progress has been steady. In December 2024 Google reported its Willow processor demonstrating quantum error correction below the threshold at which adding qubits reduces logical error rates, and in May 2025 Craig Gidney estimated that 2,048-bit RSA could be factored in under a week by a machine with fewer than one million noisy qubits, a twentyfold reduction from his 2019 estimate. Governments are acting on the risk that data encrypted today could be stored and decrypted later. NIST published its first post-quantum standards, FIPS 203, 204 and 205, in August 2024. The Canadian Centre for Cyber Security's roadmap, in effect from June 2025, asks federal departments to migrate high-priority systems to post-quantum cryptography by the end of 2031 and all non-classified systems by 2035. Most of these schemes rest on lattice problems believed hard even for quantum computers, an assumption complexity theory cannot yet prove.

Complexity and cryptography

Modern cryptography is built on complexity assumptions. A one-way function is easy to compute but hard to invert on average: given f(x) for random x, no efficient algorithm finds any preimage with non-negligible probability. Candidates include multiplication of large primes (inverting it is factoring) and modular exponentiation (inverting it is discrete logarithm). One-way functions are known to imply pseudorandom generators, symmetric encryption and digital signatures. Their existence implies \(\text{P} \ne \text{NP}\), since if \(\text{P} = \text{NP}\), inverting any efficiently computable function would be an NP search problem and therefore easy. The converse is not known: \(\text{P} \ne \text{NP}\) is a worst-case statement, while cryptography needs average-case hardness. So every secure system rests on assumptions stronger than the central open problem of the field.

SAT solvers: hard in theory, solved in practice

SAT is NP-complete, yet modern solvers routinely decide industrial formulas with millions of variables and clauses, from hardware verification, software model checking, planning, scheduling and cryptanalysis. The core algorithm, conflict-driven clause learning (CDCL), extends the DPLL procedure of lesson 10. When a branch leads to a contradiction, the solver analyses the implication graph to find the reason and adds a learned clause that prevents the same conflict elsewhere, then jumps back non-chronologically to the decision that caused it. Together with efficient data structures (two watched literals), branching heuristics that favour variables involved in recent conflicts, and periodic restarts, CDCL turns SAT into a practical tool. Annual SAT Competitions measure progress, and solvers such as Kissat and CaDiCaL are open source.

Why does this work if SAT is hard? Because NP-hardness is a worst-case statement about all instances, and industrial instances are far from worst case: they have structure, such as small separators, modularity and many redundant constraints, which learned clauses exploit. Random 3SAT formulas near the threshold ratio of about 4.26 clauses per variable are genuinely hard for current solvers at a few hundred variables, while structured formulas a thousand times larger are solved in seconds. SAT solvers have also settled mathematical questions: the Boolean Pythagorean triples problem in 2016, with a two-hundred-terabyte proof, and the value of the fifth Schur number in 2017. A theory of when hard problems are easy in practice remains one of the open challenges connecting complexity theory to engineering.

The course in one view

The course has followed a single thread: what can be computed with given resources. Finite automata, with constant memory, decide exactly the regular languages, which closure properties and Myhill–Nerode characterize completely. A stack adds nested matching and gives the context-free languages, decidable in cubic time but with undecidable equivalence. An unbounded tape gives Turing machines, the Church–Turing thesis and the boundary between decidable and undecidable, drawn by diagonalization and extended by reductions and Rice's theorem. Bounding time and space gives P, NP, PSPACE and the rest, organized by reductions and complete problems and separated, where we can separate them at all, by hierarchy theorems. The tools recur at every level: simulation and construction to show that one model can do what another does, pumping and distinguishability to show limits of finite memory, and diagonalization and reductions to show limits of computation itself.

These ideas have practical reach. A compiler engineer chooses regular expressions for tokens and grammars for syntax because of lesson 4 and lesson 6. A verification engineer accepts approximation because of Rice's theorem. An algorithm designer facing an NP-complete problem reaches for a SAT or integer-programming solver, an approximation algorithm or a parameterized method. A security engineer plans a migration to post-quantum cryptography because of Shor's algorithm and the complexity assumptions behind lattice schemes. The open problems, P versus NP, BPP versus P, the power of quantum computation and the reasons structured instances are easy, are among the most important in all of science.

Worked examples