Go to Groundby Jaidev Karthickeyan
← All notes Agents · November 2026

QuarryIf a machine can produce a landmark proof in hours, what is still scarce?

The AI shortcut that only works past the edge of the universe

Two AI labs say they broke a 27-year-old hypothesis. Their shortcut only pays off on puzzles too big to ever exist: a number with hundreds of millions of digits. The real story is that machines now write proofs cheaply, and checking them is still slow, human work.

What happened

Picture a car that is faster than yours, but only after it has driven past the edge of the universe. That is the new algorithm computer scientists are arguing about. On typical problems, its proof promises to beat brute force only once the problem's size is a number with about 301 million digits.

I first met this kind of problem in 2006, in a structural biology class on protein folding: how a chain of amino acids settles into its shape. Even a toy version, beads on a grid, had been proved hard in 1998, by Bonnie Berger and Tom Leighton and, independently, by a team including Christos Papadimitriou. The lesson was simple. Some problems are just hard, so you build around them. AlphaFold later predicted real protein shapes without breaking that rule, and shared the 2024 Nobel Prize in Chemistry. This time it runs the other way: the rule has bent, and nothing you can run got faster.

The puzzle here is 3-SAT. Picture a lock with thousands of on-off switches and a list of rules about which can sit together. Is there a setting that obeys every rule? In 1999 Russell Impagliazzo and Ramamohan Paturi proposed that there is no real shortcut: you are stuck trying key after key. That is the Exponential Time Hypothesis.

On 26 October OpenAI published "The Exponential Time Hypothesis is False", a 65-page paper whose only listed author is "OpenAI". Its unnamed model counts the winning settings with algebra instead of trying them, like weighing a jar of coins rather than counting each one. The paper says three related hypotheses fall too. Hours later Anthropic posted its own version, credited to Claude. Anthropic says Claude found its method on 16 October; OpenAI's paper is dated the 17th. Neither lab claims to have solved P versus NP.

My point is simpler. Writing a frontier proof is now fast and cheap. Checking one is not. OpenAI says it gave its model about 4,000 open problems, used three hours of ChatGPT Pro thinking per result on average, and has released 721 papers since September. Checking the headline result falls to three professors: Impagliazzo, Paturi and MIT's Ryan Williams. They are organising an open review, reportedly unpaid, and say taking part is not a seal of approval.

The arithmetic

OpenAI's own ledger (repository README, history and Lean catalogue)
Open problems given to the modelabout 4,000
Papers released (groups of related results)721 (373)
Average computer time per result3 hours of ChatGPT Pro thinking
Headline results with a machine-checked proof, 7 October300 of 719 (about 42%)
Papers withdrawn after a sign error / corrected, 7 October3 / 14
Human review status recorded in its proof catalogue"unchecked"

Every figure is OpenAI's own. The withdrawals count in its favour: the mistakes were found and fixed in public. They also show the cost of making proofs in bulk.

Going to ground

First order

It's a landmark you can't use. OpenAI's paper gives no constants, so Fabio Dias and Yvens Lima worked them out. On typical problems, the proof guarantees nothing better than brute force until the input exceeds 2 to the power of a billion, so not on any input that could ever be written down. Ruhollah Majdoddin puts Anthropic's break-even near 2 to the power 8.6 billion switches. Even his friendliest case, 2420 rules, exceeds the number of atoms in the observable universe by about 46 orders of magnitude.

So your phone, your laptop's chips and your bank's encryption work exactly as before. Theory is what changes. Results built on this hypothesis have lost their footing, and MIT's Hardness Group posted a repair, "ETH is Dead, Long Live SH", on 2 November, before the checking was done.

Second order

Writing proofs got cheap; checking them didn't. OpenAI ships its proofs in Lean, software that checks every logical step, like a calculator for proofs. But a calculator confirms your sums, not that you answered the right question. A person still has to. Williams reportedly sees "two or three alien-looking parts" still to examine. Anthropic's machine proof was reportedly checked by other copies of the same AI, a bit like marking your own homework.

The record says take care. On 7 October OpenAI withdrew three papers over a single sign error and corrected fourteen more. An independent audit of its ten August proofs found 18 chapter reviews, no confirmed serious error, one chapter needing major rework, and checking that ran deep in places and shallow in others. Machines shrink the checker's job. They don't remove it.

Third order

The value moves to whoever can be trusted to check. Peer review runs on unpaid expert time, which worked while people could only write so many papers. A lab that can try 4,000 problems at once is a kitchen cooking a thousand meals an hour with three food tasters.

Three things follow. The shared tools behind machine proofs, chiefly Mathlib, the community-built library OpenAI's proofs rely on, become core infrastructure. Credit gets contested: OpenAI leaves it "completely" to mathematicians, and its papers name no people. And the same pattern holds wherever AI writes code. Producing the work is cheap; reviewing it sets the pace.

Ears up: what to watch

  • The verdict from Impagliazzo, Paturi and Williams, and whether it covers Anthropic's proof too.
  • The break-even point: whether either guarantee drops below the size of the observable universe.
  • OpenAI's change log: withdrawals and corrections per batch, and whether "unchecked" ever changes.
  • Journals and conferences deciding what to do with papers that have no human author.

Bone of contention

Here is where I could be wrong: checking may get easier fast. Lean's check costs almost nothing, and confirming the machine proved the right statement can be quick. If the review ends within weeks, the bottleneck may be brief.

The ledger is also incomplete. Three hours is an average over results that made the catalogue; failed attempts and dollar costs aren't reported. Anthropic's details come from press reports, and either proof could still be wrong. Two labs agreeing is encouraging. It isn't proof.

In 2006 I learned that some problems are simply hard. Twenty years on, a machine says it has dented one in hours, and the verdict waits on three people, working for free.

J. & the researcher

Sources
  1. OpenAI, "The Exponential Time Hypothesis is False", dated 17 October, revised 25 October 2026: the algorithm, its running time, and the hypotheses it refutesconfirmed
  2. OpenAI math repository: README (about 4,000 problems, three hours of ChatGPT Pro thinking per result, 721 manuscripts in 373 families, credit statement), history (26 October release, 7 October withdrawals and revisions, 300 of 719 formalised) and Lean catalogue (review status "unchecked", builds on Mathlib), read 7 November 2026confirmed
  3. Dias and Lima, "Limits and Constants of OpenAI's Claimed ETH Refutation", arXiv, 31 October 2026confirmed
  4. Majdoddin, "Lowered crossover points of Anthropic's subexponential 3-SAT algorithm", arXiv, 30 October 2026confirmed
  5. MIT Hardness Group, "ETH is Dead, Long Live SH", arXiv, 2 November 2026confirmed
  6. Sienicki and Sienicki, "A Human Audit of OpenAI's AI-Generated Mathematical Proofs", arXiv, September 2026confirmed
  7. The Washington Times and XenoSpectrum and Metir AI: the review group, its open letter (no certification, unpaid) and Williams's commentsreported
  8. OfficeChai, FourWeekMBA and Dataconomy: Anthropic's paper, its 16 October date and its Lean reviewreported
  9. Berger and Leighton, "Protein folding in the hydrophobic-hydrophilic (HP) model is NP-complete", Journal of Computational Biology 5(1), 1998; Crescenzi, Goldman, Papadimitriou, Piccolboni and Yannakakis, "On the complexity of protein folding", Journal of Computational Biology 5(3), 1998confirmed
  10. The Nobel Prize in Chemistry 2024: protein structure prediction (AlphaFold) and computational protein designconfirmed
  11. Observable universe: about 1080 atoms, a common estimate used as a referencereported

Data for the chart: eth-crossover.csv. Crossover sizes are converted to digits as the base-10 logarithm of the input size, rounded up. Anthropic's own paper was not accessible from here; its details are as reported.