Computation under a clock, and the wall the master key cannot pass
One construction has run beneath the entire corpus. The diagonal proved Cantor's theorem and Russell's paradox, Gödel's incompleteness and Turing's halting problem; it forced the fixed point that limits every system turned upon itself. It is the master key. But a master key has a shape, and a shape is a limit. This volume asks the question the corpus has never asked — what are the limits of the diagonal itself? — and finds that the answer is exact, deep, and unsolved. Taken into the world of feasible computation, bounded by a clock, the diagonal still triumphs: the hierarchy theorems, proved by a clocked diagonal, hand us real and unconditional separations. But at the central question of that world — whether finding is as easy as checking, whether P equals NP — the diagonal fails, and we can prove it fails. The relativization barrier shows that the tool which opened every other door cannot open this one. The limit-finder is itself limited, and the corpus closes not at a terminus but at a living frontier, where the master key has met its match and new keys are still being forged.
the reflexive turn · the diagonal's own boundary — the time and space hierarchy theorems, the diagonal triumphant under a clock; P versus NP, the question it cannot reach; the relativization barrier of Baker–Gill–Solovay, the diagonal's precise limit; why a black‑box method is blind to the structure of computation; the further walls of natural proofs and algebrization; and the conservation law in its final form — the limit relocating into the very method that finds limits
The Ceiling asked what is computable at all; this asks what is computable within a budget. It is a different regime, with a different fate for the diagonal — and the difference is the subject of the volume.
a new regime for an old engine The diagonal corpus and its complement studied computability in principle: whether a problem can be decided by any algorithm whatsoever, with no limit on time or memory. The halting problem is undecidable in that absolute sense; the arithmetical hierarchy stratifies what unbounded computation can reach. But there is a second, harsher question, the one that governs whether a computation is of any practical use: not can it be done, but can it be done in time we can afford? This is the regime of complexity — computation under a clock, sorted by how its cost grows with the size of the input. And the diagonal, the corpus's master engine, enters this regime with its character intact but its fate transformed. Here it both triumphs and, for the first time anywhere in the corpus, fails — and the precise line between the triumph and the failure is one of the deepest facts in all of mathematics.
the reflexive turn There is something fitting in ending here. The corpus has spent its whole length wielding the diagonal as an instrument — pointing it at set theory, at arithmetic, at computation, at truth, and reading off the limit it forces in each. The instrument was never itself examined. But the diagonal is a method, and every method has a reach and an edge, and the most honest thing a study of limits can do is turn its instrument upon itself and ask where it stops. Complexity theory is where that question becomes precise, because here, uniquely, there is a concrete separation the diagonal manifestly should prove — the difference between solving and verifying — and manifestly cannot. The relativization barrier names the reason exactly. So the final movement of the corpus is the diagonal turned upon the diagonal: the limit‑finder finding its own limit, the master key discovering the one shape of lock it was never cut to open. And the gap it cannot close is not a settled fact but the discipline's greatest open problem, so the corpus ends pointed forward, at the edge of the known.
The argument runs in three beats. First, the diagonal succeeds: with a clock added — a machine that simulates another and flips the answer within a fixed time budget — it proves the hierarchy theorems, that strictly more time and more space buy strictly more computational power. These are unconditional separations; we genuinely know, by the diagonal, that some problems require exponential time. Second, the diagonal stalls: at P versus NP — determinism against nondeterminism at the same polynomial budget — the clocked diagonal has no purchase, and the question has resisted for half a century. Third, the diagonal is shown to be provably insufficient: the relativization barrier demonstrates that no argument of the diagonal's kind can settle the question, because such arguments treat machines as black boxes and the answer to P versus NP depends on what is inside the box. After that come the deeper walls, and then the reckoning — the conservation law of The Law reaching its widest form, the forced limit relocating one last time, out of theories and models and logics and into the method itself.
Add a clock to the diagonal and it proves that more time, and more space, buy strictly more power. These are not conjectures but theorems — unconditional separations, the diagonal working exactly as it always has, only bounded.
simulate, and flip — on a budget The halting argument built an uncomputable set by simulating each machine on its own description and flipping the answer. The time hierarchy theorem does the same with a stopwatch. Build a machine D that, on input ⟨M⟩, simulates M(⟨M⟩) for g(n) steps and outputs the opposite of whatever M does. Then D runs in time g — that is its whole budget — yet differs from every machine running in the smaller time f, because on input ⟨M⟩ it has time enough to watch M finish and contradict it. The only subtlety is the cost of simulation, a logarithmic factor, which is why the gap required is f log f = o(g). The diagonal, clocked, separates the classes.
the clocked diagonal — D differs from every machine on its own input
Between solving and verifying lies the most famous open problem in the field. The hierarchy theorems separate different budgets; this asks something they cannot see — whether two modes of computation differ at the same budget.
finding versus checking Two classes frame the question. P is the problems a computer can solve in polynomial time — feasibly, by any reasonable measure. NP is the problems whose solutions a computer can verify in polynomial time: given a candidate answer, it can check the answer quickly, even if finding one might be hard. Every solvable problem is verifiable — hand the verifier the solution the solver found — so P ⊆ NP. The question is whether the inclusion is strict. Is P = NP? Is every problem whose answers can be checked efficiently also one whose answers can be found efficiently? Is the act of searching no harder, in the end, than the act of recognizing? On it hang the security of every cipher, the tractability of ten thousand optimization problems, and the question of whether mathematical discovery is, at bottom, mechanical. Almost everyone believes P ≠ NP — that finding is genuinely harder than checking — and no one can prove it.
why the clocked diagonal stalls The hierarchy theorems were separations of budget: a machine with time g beats every machine with the smaller time f, and the diagonal manufactures the witness by out‑simulating the weaker machines. But P and NP sit at the same budget — both polynomial — and differ only in mode: NP is permitted to guess, to branch nondeterministically and accept if any branch does. The diagonal's trick is to simulate a machine and flip it, but to diagonalize against all of P one would need to simulate an arbitrary polynomial‑time machine and still have polynomial time left to flip — and to place the result in NP rather than somewhere far above it. The budgets are too close and the modes too alike; the simulate‑and‑flip that cut cleanly between f and g finds nothing to grip between determinism and nondeterminism at one budget. The diagonal stalls, and the question is left standing. The next section explains why this is no accident of cleverness but a provable wall.
Why does the diagonal stall at P versus NP? Not for want of ingenuity. Baker, Gill, and Solovay showed that no argument of the diagonal's kind can ever succeed — by building two worlds in which the answer is opposite.
machines with an oracle Give a machine a magical subroutine — an oracle for some set A — that answers "is x in A?" instantly, for free. Every complexity class has a relativized version: PA and NPA are the problems solvable, and verifiable, in polynomial time with the oracle on call. Now observe the crucial fact about the diagonal: it relativizes. Its arguments — simulate a machine, flip the answer — never look inside the machine; they treat it as a sealed box that takes inputs and returns outputs. Hand every machine the same oracle and the simulation still goes through unchanged, because the oracle is just part of the box. So any theorem the diagonal can prove, it proves relative to every oracle at once: a diagonal proof of P = NP would establish PA = NPA for all A, and a diagonal proof of P ≠ NP would establish the separation for all A. The method cannot tell the oracles apart.
two worlds — and the diagonal cannot tell which is ours
The barrier is not a quirk; it follows from what the diagonal is. The very feature that made it the master key — that it works against any system whatsoever — is exactly what bars it from this door.
the source of the diagonal's power Look back across the corpus and ask why the diagonal worked so universally. Against Cantor's sets, Turing's machines, Gödel's proofs, the diagonal needed only one capacity: to take a system's own description, run the system on it, and produce the opposite. It never inspected the internals — never used a special feature of sets, or of programs, or of proofs. That is precisely its strength: a method that ignores internal structure works against everything, because it asks of every system only the one thing every reflexive system can do, turn upon itself. The diagonal is the universal limit‑finder exactly because it is a black‑box method.
and the source of its blindness But P versus NP is not a black‑box question. To separate them is to prove that some particular problem — satisfiability, say — has no fast deterministic algorithm, and that is a claim about the internal structure of all possible algorithms: what the architecture of efficient computation can and cannot express. A method that refuses to look inside the box cannot prove a fact about what is inside it. Relativization is the exact formalization of this: an oracle is a way of changing what is inside the box while leaving its interface unchanged, and the diagonal, blind to internals, cannot see the change — so it gives the same answer in worlds where the truth differs. The diagonal's universality and the diagonal's blindness are one property, named twice. It opens every lock that can be opened by turning a system on itself; it cannot open a lock that requires seeing the mechanism within. The master key has a shape after all, and the shape is "self‑reference, structure‑blind."
This casts the entire corpus in a sharper light. Every limit the diagonal proved — uncountability, undecidability, incompleteness, the hierarchy theorems — was a limit that could be forced without looking inside the system, by self‑reference alone. The diagonal found exactly the limits that are visible from the outside, that follow from a system's mere capacity to refer to itself, and it found all of them, which is why it seemed omnipotent. But there is a second kind of limit, invisible to self‑reference: limits that depend on the internal architecture of a system, on what its mechanisms can and cannot do. P versus NP is the first great instance the corpus has met of a limit of the second kind — a question whose answer lives inside the box, where the diagonal cannot reach. The corpus's master tool was never omnipotent; it was perfectly fitted to one family of questions, the family of self‑reference, and that family, vast as it is, has a boundary. We have just crossed it, and on the far side the diagonal falls silent — not defeated, but simply out of its domain.
Relativization is only the first wall. Each technique that climbed over it met another, and the sequence of barriers is a map of why the question has resisted for half a century — and what a solution would have to evade.
past the first wall, two more The relativization barrier was not the end of the story but the start of a pattern. Techniques were found that do look inside the box — arithmetization, which lifts Boolean functions to polynomials over a field and reasons about their algebra — and these broke through, proving non‑relativizing theorems like IP = PSPACE. But each new method, examined, turned out to be stopped by a new barrier. The combinatorial lower‑bound methods ran into the natural proofs barrier: any property usable as a lower bound that is efficiently testable and holds for most functions would, by that very fact, break the pseudorandom generators on which modern cryptography rests — so if one‑way functions exist, those methods cannot separate P from NP. And the arithmetization methods that broke relativization ran into algebrization: they survive even when each oracle is replaced by a low‑degree polynomial extension of itself, and that survival, Aaronson and Wigderson showed, is incompatible with resolving P versus NP. Three walls, each formalizing a class of techniques and proving it insufficient.
the three barriers — the gauntlet a separation must run
It is worth being exact about what these results establish, in the corpus's discipline of separating the proved from the suggested. The barriers do not show that P ≠ NP is unprovable, nor that it is independent of arithmetic, nor that it is false. They show something narrower and stranger: that whole families of techniques — the ones we have, the ones that proved everything else — are provably unable to settle it. Relativization bars the black‑box methods; natural proofs bar the constructive‑combinatorial ones, modulo cryptography; algebrization bars the arithmetic ones. Each is a theorem about the reach of a method, not about the truth of the conjecture. Together they explain why fifty years of effort by the field's best minds has not closed the gap: not because the problem is unsolvable, but because every tool we have brought to it is, demonstrably, the wrong shape. The diagonal is the first of those tools, and its barrier — relativization — is the one this corpus was always destined to reach, because the diagonal is the corpus's own engine, and we have followed it all the way to its edge.
The instrument has been turned upon itself, and it has an edge. What remains is to name what that means for the whole — and to leave the corpus, rightly, at the open frontier rather than a closed door.
the conservation law, in its widest form The Law stated that the forced fixed point can never be deleted, only relocated, and the corpus has now watched it migrate across every level of the foundations. It began in theories: arithmetic cannot prove all the truths of its intended model — incompleteness. Pressed, it moved to models: no first‑order theory can pin that model down among the multitude. Pressed harder, into logics: strengthen to second‑order and capture the model uniquely, and the incompleteness reappears as the unaxiomatizability of the logic itself. And now, at the last, it has moved into the method. The diagonal — the very instrument that found the limit at every prior level — meets a limit of its own: it cannot resolve P versus NP, and the relativization barrier proves it cannot. There is no level at which the limit dissolves; there is only the next stronghold for it to occupy. Surrender the theory's completeness and it takes the model; surrender the model's plurality and it takes the logic; bring the sharpest instrument we have and it takes the instrument. This is the conservation law in its final and widest form: the gap between a formal system and what is so is invariant under every attempt to close it, including the attempts to study it.
no view from outside This is the deepest reflexive turn in the corpus, and its quietest. We set out to map the limits of formal systems, and the map was drawn with one instrument, the diagonal. To find that the instrument itself has a limit — that there are questions about computation it provably cannot answer — is to find that the inquiry is subject to its own conclusion. There is no privileged vantage, no view from outside the system of systems, from which all limits could be surveyed by a method exempt from limits. The limit‑finder is inside the world it studies, and shares its condition. The diagonal taught us that no system can fully grasp itself; turned upon the project of grasping systems, it teaches that no method can fully grasp the methods either. The corpus's subject was always the unbridgeable gap between a formalism and its object, and the final instance of that gap is the one between our tools and the truths they are built to reach.
the open frontier And so the corpus ends, deliberately, not at a sealed terminus but at a living edge. Incompleteness is proved; the multitude is proved; the keystone is proved; the conservation law is proved. But the diagonal's limit at P versus NP is not the end of a story — it is the beginning of one still being written. The barriers tell us why the question is hard, not what its answer is. Beyond relativization, beyond natural proofs, beyond algebrization, the frontier of complexity theory is the search for techniques of a kind we do not yet possess — methods that look inside the box, that exploit structure the diagonal is blind to, that might one day cut where the master key cannot. The single construction that ran beneath this entire work — g(x) = α(φ(x)(x)), evaluate the system at itself and twist — opened set theory and arithmetic and computation and truth, and forced the fixed point that limits them all. Here, at its own edge, it has shown us the shape of what it cannot do, and pointed past itself to the work that remains. The diagonal is complete. The frontier is open. And the gap it has measured, level after level, is the permanent condition of every formal thing that reaches for a truth beyond its own walls.
One construction ran beneath the corpus, and this volume found its edge. The diagonal — master key to every prior limit, from Cantor to Gödel to the hierarchy theorems it still proves cleanly under a clock — cannot resolve the central question of feasible computation, whether finding is as hard as checking, whether P equals NP. And the relativization barrier proves it cannot: there are two worlds, one where the classes collapse and one where they part, and the diagonal, blind to the internals of the machines it simulates, runs the same argument in both and so can decide neither. Its universality and its blindness are one property; it opens every lock that yields to a system turned upon itself, and no lock that requires seeing the mechanism within. The barriers of natural proofs and algebrization mark the further walls, a gauntlet no known technique can run. And the conservation law reaches its widest form: the forced fixed point, having migrated from theories to models to logics, relocates one final time into the method itself — for even the limit‑finder is limited, and there is no view from outside. The corpus closes at the open frontier. PA = NPA, PB ≠ NPB — the diagonal's own boundary, written in two worlds it cannot tell apart.