Draft. Thinking aloud. This is the beginning of a research statement, not the end of one.
This morning, Nvidia committed five billion dollars to Safe Superintelligence, the company founded by Ilya Sutskever, in exchange for equity and a promise to multiply its compute tenfold within a year. SSI has, to date, shipped no product, published no research, and demonstrated no commercial traction. This is not a criticism of SSI — it is simply what the reporting says. Five billion dollars and a tenfold increase in compute for a company whose founder went on record last year to say that the age of scaling is ending. One admires the internal consistency of an industry that responds to “more compute will not be enough” by purchasing more compute. Nvidia’s own stock closed down about five percent on the day, which suggests the market has at least a rudimentary sense of irony even when the participants do not.
Meanwhile Meta is spending seventeen billion dollars a quarter on capital expenditure and promising “personal superintelligence for everyone,” a phrase that has the same relationship to engineering that “subterranean opportunity space” has to a hole in the ground.
Let us talk about cranks.
A Taxonomy
When I was younger and read physics for pleasure, there was a reliable genre of correspondence: the letter, usually typed, usually with underlining, announcing the discovery of a perpetual motion machine. The pleasure was not in the discovery — there was never a discovery — but in the classification. You read the argument, you found the error, and you filed the author.
A crank of the first kind claims a machine that produces energy from nothing. He violates the first law of thermodynamics: conservation of energy. His diagram has a wheel with weights on it, and if you follow the weights around, they do not come back to where they started.
A crank of the second kind is more sophisticated. He concedes conservation of energy. He does not claim to make energy; he claims only to extract it — from the ocean, from the ambient air, from the vast reservoir of heat that surrounds us and is admittedly free. He violates the second law. He has invented a machine that takes disorder and returns order, at no cost, and he has not noticed.
The second kind is always the more interesting letter, because the error is deeper and the author is usually cleverer.
I propose that the same taxonomy applies, exactly and usefully, to claims about computation. And I propose it in a spirit of genuine intellectual charity, because the classification is not an insult. It is a diagnostic procedure, and I have spent twenty years building diagnostic procedures.
A crank of the first kind in computer science claims to solve NP-hard problems in polynomial time. He violates P ≠ NP. This is technically a conjecture rather than a law, but it is the best-supported conjecture in the subject, and if you propose to overturn it you had better bring a proof rather than a benchmark. These letters still arrive. They are honest, at least, about what they claim.
A crank of the second kind concedes the complexity classes entirely. He agrees that travelling salesman is NP-hard, that circuit minimisation sits at the second level of the polynomial hierarchy, that model counting is #P-complete. He agrees to all of it, cheerfully, and then explains that his system does not need to solve the worst case, because it has learned the structure of real instances. It has absorbed, from a corpus, the shape of the answer. It will simply produce the correct output without searching for it.
This is the machine that extracts work from a single heat bath. He has proposed to obtain a certificate — a guarantee, a proof, a thing you can check — from a process that produces no certificate, and he has not noticed the difference between an answer and an answer you can verify. He has confused a plausible output with a sound one. The energy is free, the ocean is vast, and the machine will run forever.
There is now a third kind, unknown to classical thermodynamics, who does not claim to solve anything at all and raises five billion dollars regardless. He violates no law of physics. He violates only the conservation of shareholder value, and that quantity was never conserved to begin with.
I will spend the rest of this post explaining why I believe the second-kind classification is correct, and what I intend to do about it, which is the actual purpose of the exercise.
Where I Have Been
Nowhere intellectual. I travelled, I did summer things, I saw people, I did not write. The blog went quiet after Delft and the Cerebras IPO and the AI café ordering eggs for a kitchen with no stove. I recommend the pause. Things settle.
I am back, and I am back with a specific problem: I am defining projects, looking for gigs, and — most importantly — returning to research. Returning to research requires knowing what your research is, which requires writing it down, which is what this is. Consider it a first draft with the seams showing.
The Universe Is an Optimisation Problem
Start where physics starts. The principle of least action says that a system evolving from one configuration to another takes the path that makes the action stationary. Fermat’s principle says light takes the path of least time. Soap films find minimal surfaces. The Euler–Lagrange equations are what you get when you set a derivative to zero and solve.
This is not a metaphor. The universe really does compute, and what it computes is the stationary point of a functional. Newtonian mechanics, electromagnetism, general relativity, the Standard Model — all of it can be written as “here is a Lagrangian, now find where the variation vanishes.” The universe is a very large, very fast, very well-conditioned optimiser, and the method it uses is the derivative.
Which is to say: the universe does gradient descent.
And this is precisely the point at which the argument turns, because the second observation follows immediately from the first:
The universe does gradient descent, and therefore the universe does not solve NP-hard problems either.
The evidence is everywhere, and it is embarrassing:
- Soap films do not solve Steiner tree. The folklore claim — dip a frame in soapy water, get the optimal network — is false, and it has been tested rather than argued about. Films get stuck in local minima. They find a minimal surface, not the minimal surface, and which one depends on how you pulled the frame out of the bucket.
- Proteins misfold. Levinthal’s paradox observes that a protein cannot be searching its conformation space, because the search would outlast the universe, and yet folding happens in microseconds. The resolution is that nature is not searching — it is rolling downhill on a funnel-shaped landscape. It works most of the time. When it does not work you get amyloid plaques and prions, which are what a local minimum looks like from the inside.
- Spin glasses do not find their ground state. Determining the ground state of a three-dimensional Ising spin glass is NP-hard. A real piece of spin glass, cooled in a real refrigerator, does not find it. It ages, it hystereses, it gets stuck, and it stays stuck for geological time.
The universe is a superb gradient descender and a hopeless combinatorial optimiser, and these are the same fact stated twice. This is why the “analog computer solves NP-complete problems” genre is a permanent fixture of the crank literature: it is the exact physical analogue of the perpetual motion machine, and it fails for a reason of the same character.
Integers Are Where It Gets Hard
I have spent an unreasonable fraction of my professional life on this, so permit me some specificity.
Gradient descent needs three things: a continuous domain, a differentiable objective, and a landscape on which local information is informative. Given those, it is magnificent. Modern deep learning works not because anyone found a clever algorithm but because, in sufficiently high dimension and with sufficient overparameterisation, the loss landscape turns out to be benign — mostly saddle points rather than bad local minima, mostly connected basins. You take the derivative, you step, you repeat, and it works. Nobody fully knows why it works this well. It works.
Now require the variables to be integers.
Every one of the three things breaks at once. The domain is the vertices of a hypercube; there is no gradient on a vertex. The objective is defined only at those vertices; there is nothing to differentiate. And local information stops being informative — flipping one bit can move you anywhere.
The standard rescue is relaxation: let your binary variables live in [0,1], solve the resulting continuous problem, and hope. This is the foundation of half of operations research and it is genuinely powerful. But notice what it gives you. It gives you a bound, not an answer. The distance between the relaxed optimum and the true integer optimum is the integrality gap, and closing it is the entire discipline: branch and bound, cutting planes, Lagrangian relaxation, column generation, symmetry breaking, forty years of the Mixed Integer Programming literature. The relaxation tells you where the answer cannot be. Finding where it is requires search.
Nor can you simply round and call it a day. For a large class of problems, no polynomial-time procedure can get you close. Håstad’s result on MAX-3SAT says that beating a 7/8 approximation is itself NP-hard. This is not “we have not found the algorithm yet.” This is a theorem about what rounding can do.
And where does the guarantee come from, when you have one? From duality and from exhaustion. LP duality gives you a certificate: a dual feasible solution that proves no better primal solution exists. Branch and bound gives you a certificate: a search tree, every branch of which was closed by a bound or a proof of infeasibility. A SAT solver that reports UNSAT can hand you a resolution refutation and you can check it independently with a program you wrote yourself in an afternoon.
A gradient step produces no certificate. It cannot. It is a local move on a continuous surface, and its output is a slightly better point, not a proof about all other points. Ask it for a proof and it has nothing to give you, because proofs are not the kind of object it manufactures.
Which Brings Us to the Chatbots
The training objective of a large language model is cross-entropy on next-token prediction. Gradient descent descends that. There is no theorem — not a weak one, not a conditional one, not one anybody has attempted — connecting low cross-entropy loss to correctness of a mathematical argument. The loss went down. That is what has been established.
There is also a structural point that deserves more attention than it gets. A transformer forward pass is a fixed-depth circuit. Fixed-depth, polynomial-size, threshold-gated circuits are the class TC0, and TC0 does not contain NP-hard problems unless a great deal of complexity theory is wrong. Each token costs a bounded amount of computation, and no amount of parameter count changes the depth.
The escape hatch is chain of thought: use the context window as a tape and you recover, in principle, a general computation. Fine — but now you are running a Turing machine on a substrate with no error detection and no error correction, and every step is sampled rather than derived. This is not an incidental defect to be engineered away. Hallucination is what an unverified tape looks like. It is the same phenomenon as a soap film in a local minimum: the process ran, it terminated, it produced something, and nothing in the process was ever obliged to produce the right thing.
So: chatbots will not do theorem proving. And here I want to be precise, because the imprecise version of this claim is itself crankery, and I would rather not be classified by my own taxonomy.
What is actually happening in the Lean ecosystem right now is that language models propose and kernel checks. Models generate candidate formalisations and candidate tactic scripts; a small, auditable, deterministic proof kernel accepts or rejects them. Some real results have come out of this, including formalisations of things that were open. This is genuine and I have no interest in denying it.
But look at where the guarantee lives. It lives in the kernel. It lives in a few thousand lines of code that implement a type theory and can be read by a human being in a week. The model is a proposal distribution — an extremely expensive, occasionally brilliant heuristic for generating candidates. It is playing the role that a branching heuristic plays inside a SAT solver: it makes the search faster and it makes no promises. Take the kernel away and you have a machine that emits confident LaTeX.
The gradient proposes. The verifier disposes. Anyone who tells you the gradient is doing the proving has confused the two, and the confusion is exactly the second-kind error: mistaking a plausible output for a sound one, and expecting a certificate from a process that emits none.
So What Am I Actually Doing
Here is the research statement, in draft.
The interesting problems live at the boundary between the continuous and the discrete, and almost nobody works there. The continuous side is well served — that is physics, that is simulation, that is the entire deep learning industry. The discrete side is well served by the SAT, SMT, QBF, and MIP communities, who are serious people doing serious work with certificates. The boundary is thinly populated and it is where the real systems are.
My own work has been sitting on that boundary for twenty years without my having named it properly:
- Model-based diagnosis is exactly this shape. The fault hypotheses are discrete — this component is healthy or it is not, and there are 2n of them. The behaviour is continuous — ODEs, DAEs, SPICE models, thermal gradients, feedback. Lydia-NG exists because Boolean models are wonderful for switching circuits and useless for anything physical. A hybrid diagnostic engine is a mixed-integer problem wearing a lab coat.
- Exact synthesis — qbf-designer — is Σ2p-complete and gets exact answers where Vivado and Yosys get heuristic ones. Five LUTs where the heuristic finds six. The point is not that five is smaller than six. The point is that I can prove there is no four.
- Diagnostic probability is a counting problem, and counting is harder than deciding. The posterior of a diagnosis is a ratio of model counts: how many assignments of the internal signals are consistent with the model, the observation, and this fault hypothesis, over the total. That is #P-complete. LyDiA got this wrong for a decade — it multiplied independent priors together and called the product a probability — and the modern llogic packages fix it. What I still cannot resolve is that every diagnostic probability is therefore a rational, a ratio of two integers, and physical failure rates are not obviously rationals at all. That one keeps me up.
- Technology mapping for Verilog and VHDL is where I think the near-term commercial value is, and my Delft friends have graciously confirmed it is not entirely a hallucination.
And the part I need to think harder about: where the learned heuristics legitimately belong. They belong inside the sound framework, not instead of it. Branching order. Variable selection. Restart policy. Which cut to add. Candidate proposal for a kernel to check. All of these are places where a model that is right 70% of the time makes a sound solver dramatically faster and never makes it wrong, because the soundness was never the model’s job. That is a research programme I can defend to a referee, and it is roughly the opposite of the one currently being funded at five billion dollars a pop.
The universe does gradient descent, and it is very good at it, and it cannot factor a number. The industry has built a magnificent gradient descender and is now surprised that it cannot factor a number either.
More soon, and with code. As always, everything I discuss is reproducible, which continues to distinguish it from most of what is published within a fifty-mile radius of here.
Ceterum censeo slopem esse delendam.
(Cato the Elder ended every speech in the Roman Senate with “Carthage must be destroyed” — regardless of the topic. This is that, but for AI slop.)
Leave a Reply