Living Below the Ceiling

The last two topics drew two ceilings: questions no program can answer, and questions every known program answers too slowly for large inputs. Engineers ship anyway. Package managers resolve versions, schedulers pack containers onto machines, and delivery routes are planned every morning, all by changing what they ask for.

And one whole field runs on hardness itself. Every encrypted connection you opened today is safe because some problems are believed to be hard. This topic is the toolkit for working under the ceilings, and then the end of the book: one last look at the spine, and where each chapter's ideas are put to work.

Approximation With a Guarantee

The first move gives up the optimum and keeps a promise. To cover every edge of a graph with as few vertices as possible, repeatedly take an edge that is not yet covered and add both of its ends. The result is never more than twice the size of the smallest cover. Christofides' algorithm of 1976 plans a round trip that is never more than 1.5 times the shortest, for any distances where going direct is never longer than a detour. First-fit decreasing bin packing, met in Chapter 9, sorts the items largest first, drops each into the first bin with room and never uses more than 11/9 of the optimal number of bins plus less than one, about 22% more.

Each of these runs in polynomial time, and each carries a proof of how far from the best it can land. The price is a known, bounded amount of waste, stated before the run. That makes an approximation a planning tool rather than a gamble: you can tell the finance team that a large packing uses at most about 22% more hosts than the best possible one, and be right.

Heuristics Without One

The second move drops the promise too. Greedy choices from Chapter 9, local search that keeps swapping two stops or two jobs while the result improves, and random restarts of that search come with no guarantee about the worst case. They are often excellent on real inputs, and they are what most production systems run.

Kubernetes places a pod by filtering out the nodes that cannot take it and scoring the rest, then picking the best score. It does not solve the packing optimally, and nobody wants it to: a scheduler that searched every placement would never place anything. The catch is that "often excellent" is measured, not proven. A heuristic tuned on last year's workload needs watching on this year's.

Solvers

The third move hands the problem to a general engine. SAT solvers, integer-programming solvers and constraint solvers carry decades of engineering: they learn from each dead end, prune whole regions of the search and on real inputs routinely finish problems that exhaustive search could not touch. You encode the problem, hand it over, and get an answer, or the best answer found so far when a time limit expires.

Package managers are the everyday case. openSUSE's zypper and Fedora's dnf resolve dependencies with libsolv, a SAT-based solver. Newer resolvers, including the one in uv, use PubGrub, a search that learns a new rule from each conflict so it never repeats the same mistake. Solvers cost the work of encoding the problem, and nobody can promise their run time: on the rare input built to be hard, the solver is exponential like everything else.

Changing the Problem

The strongest move is to ask an easier question. Go's module system chose minimal version selection, described by Russ Cox in 2018: take the oldest version of each module that satisfies every stated requirement. That turns an NP-complete resolution into a walk over a graph, linear in the size of the requirements. In exchange, a build never picks up a newer release unless someone asks for it.

The same move works elsewhere. Restrict the input: bounded loops against the halting problem, a small n against exponential search. Accept "probably": a Bloom filter from Chapter 9 answers "definitely not" or "probably yes" in a fraction of the memory. Put a time box on a search and return the best answer found when it expires. Each one trades a property you did not need for a cost you can pay.

Hardness as a Feature

Cryptography turns the ceiling into a wall. A 128-bit key has 2 to the 128 possible values. At a billion billion keys a second, trying them all would take about ten trillion years, hundreds of times the age of the universe. RSA rests on the belief that factoring large numbers is slow. That has never been proved, and factoring is not even known to be NP-complete.

Nor would NP-completeness be the right foundation. It is a worst-case statement about the hardest inputs, while a key must be hard to break for typical, randomly chosen keys. Cryptography needs problems that are hard almost all the time, and it rests on assumptions that thousands of researchers have attacked without success, which is a different kind of evidence from a proof. A large quantum computer running Shor's algorithm of 1994 would break RSA and elliptic-curve cryptography, which is why NIST published its first post-quantum standards, FIPS 203, 204 and 205, in August 2024. That is the only line this book spends on quantum computing. The practice of all this is CyberSecurity Deep Dive, Chapter 2, Cryptography in Practice.

The Spine, Once More, and Where to Go Next

Every choice a computer makes has a price, and the price comes from the layer underneath. A dictionary lookup is fast because of a hash table, which is fast because an array index is one multiplication and one memory read, which is fast only when that memory is already in cache. The second read of a file is fast because the kernel kept its pages. Two threads lose an update because adding one is three instructions. At the bottom of every such chain sit the two ceilings of this chapter, and engineering is choosing which price to pay below them.

Each part of the book has a course that puts it to work. The machine, memory, operating system and concurrency chapters continue in Linux Deep Dive: Chapter 6, Processes and Signals, Chapter 13, Performance and Troubleshooting, and Chapter 14, The Kernel and Containers. Reliable delivery continues in Networking Deep Dive, Chapter 5, The Transport Layer. The B-tree continues in PostgreSQL Deep Dive, Chapter 8, Indexes. Exactly-once delivery and its absence continue in Backend Deep Dive, Chapter 7, Failure by Design.

Memory safety and hardness continue in CyberSecurity Deep Dive, in Exploitation Basics in Chapter 5 and in Chapter 2's cryptography. The packing heuristics of this page are the subject of Kubernetes Deep Dive, Chapter 5, Scheduling and Scaling. The language Chapter 13 ran, taught as a language, is Python for Beginners. And many machines working as one, left out of this book on purpose, belong to a System Design course that is on the roadmap and not yet written.

This book ends where it began, with one question: what does it cost, and why? You now have an answer for every layer from the transistor to the ceiling over all computation. The next time a service is fast in testing and slow in production, you know which layer to look at first.