Exponential Time Hypothesis is false, OpenAI and Anthropic say

Two labs now say their internal models overturned a 25-year-old assumption at the base of computational complexity. The people who invented that assumption are the ones checking the work.

OpenAI published three research results on Monday that it says its internal models produced, and the sharpest one claims the Exponential Time Hypothesis is false. The company says the disproof was generated on October 16 and formalized in Lean a day later, and it has published both the writeup and the proof in a public repository, according to OpenAI's announcement. The people checking it are the people who invented the conjecture.

ETH says the Boolean satisfiability problem has no real shortcut: every added variable doubles the worst case, and no algorithm does meaningfully better than brute force. It is a stronger claim than P ≠ NP and a far more useful one. Hundreds of papers in graph theory, computational biology, databases and computational geometry derive "you cannot do better than this" results by assuming ETH holds. If it falls, those results are not wrong — they are simply no longer proven.

OpenAI's arrangement for the review is the unusual part. Russell Impagliazzo and Ramamohan Paturi at UC San Diego, who proposed ETH with Francis Zane in 2001, are shepherding the examination alongside MIT's Ryan Williams, who has spent a career refuting strong versions of the same hypothesis. The three say they have signed no NDAs, are working unpaid, will share interim findings as they go, and that their involvement is not an endorsement. At their request, OpenAI released all the raw data — the paper and the Lean proof — and agreed to fund a conference on what the result means for the field. The company also put $5 million into the Simons Foundation's effort to help mathematicians navigate AI-era results.

There is a second claimant. Anthropic's formal-math repository now carries A 2^o(n) Time Algorithm for 3-SAT, credited to "Claude (Anthropic)", which gives a deterministic algorithm deciding 3-SAT in sub-exponential time and, harder, counts satisfying assignments in 2^O(n log log n/√log n) — the same refutation, published as an Apache-2.0 artifact. Its README says the result was "discovered by an internal research Claude model" and that the Lean 4 formalization was written by AI models. OpenAI dates its disproof to October 16 and the formalization to the 17th. Anthropic has not publicly dated its discovery, and neither company has commented on the other's result.

Anthropic's repo is the more checkable of the two, which matters. It pins Lean v4.33.1 and the matching Mathlib, documents an eight-minute build on 24 virtual CPUs with a peak of about 7 GB, and its CI runs a second, independently written kernel to re-check the proofs plus a comparator that verifies the Lean statements match the paper's numbered theorems. One file prints the axioms each theorem depends on — Lean's three standard ones, if the build is clean. Any complexity theorist with a laptop can reproduce that in an afternoon, and Claude Opus 5.5 can apparently rederive the argument from a condensed sketch included in the README.

Lean settles less than it appears to. It proves the theorem as written; it cannot tell you the formal statement captures the problem a human meant. That gap is where the real review happens, and it is why the Impagliazzo group's role is not ceremonial.

What the result does not do is make anything faster. The bound is sub-exponential — 2^o(n), not polynomial — so P versus NP is untouched, and OpenAI's own writeup says the work "may help guide the search for better algorithms" while turning that into practical gains "will require significant further research." Real SAT solvers already handle formulas with millions of variables, because industrial instances are far easier than the worst case ETH describes. Williams told followers on X that nobody knows yet what developers will notice; he thinks serious practical progress is plausible within 12 months, "or we may see nothing of the sort." Matthew Green's reaction was blunter: odd that so many breakthroughs arrived with not one result in practical cryptanalysis.

The other two results are smaller stories with bigger claims attached. OpenAI says its models proved the local smoothing conjecture — proposed by Christopher Sogge in 1991, previously known only in two dimensions — in every dimension, which would also settle the Kakeya and Stein restriction conjectures in all dimensions. And it says they proved the existence of quantum chromodynamics and a unified completion of the Standard Model in four dimensions, including pure Yang-Mills theory, which is half of a Millennium Prize problem. The mass gap, the other half, is untouched, so no $1 million.

My read: the result that matters here is procedural. OpenAI is shipping model output as "raw research data" and outsourcing the meaning to named humans, which is a real answer to the criticism that followed its October 6 math release — we covered that credibility problem earlier this month, Mathematicians ask whether OpenAI can be trusted with unpublished math — and an admission that a proof nobody can attribute is worth less than a proof everybody can check. The risk is a two-tier field: whoever gets invited to shepherd sees the work months before everyone else, and OpenAI says so itself. The Lean proofs and Anthropic's buildable repo are the counterweight. Verification is becoming the product.

The same prompt can cost 1.5 to 5 times more in one language than another — and up to 17 times more once you leave the top 20. That is the finding Rest of World reports from the Coalition for Language Equity in AI Research, which measured how many tokens leading models burn to do identical work. Across the 200 languages tested, the gap widened to 17 times in one model; Burmese, Tibetan, Tifinagh, Khmer, Lao and Ol Chiki were worst served in nearly every system. Latin-script languages collect a subsidy they never earned: Asturian, with almost no training data of its own, benefits from Italian and Spanish.

This is a margin problem before it is a fairness problem. A team in Bengaluru shipping the same product as a team in Austin pays a surcharge on every prompt and completion, and that ratio does not move when per-token prices fall. It eats context too: a tutoring app that keeps a student's history burns its window faster in one language, which degrades the answers. Independent work points the same way — a September paper on token premiums in French and regional languages found the pattern across 2026 tokenizers. No lab has committed to redesigning a tokenizer over it, which is the tell: a new vocabulary means retraining, and nobody wants to spend that on languages with no revenue.

What to watch: whether the Impagliazzo group's interim notes agree with the Lean statements, and whether any lab starts publishing per-language token counts the way it publishes benchmark scores.

If a proof can be checked by a machine but only interpreted by invitation, who should hold the keys? Write to us via our contact page.