Two AI labs refute a conjecture from 1999. Why the way to check it is the real news

TL;DR. On October 26, OpenAI announced that an internal model had refuted the Exponential Time Hypothesis. The computer science conjecture dates from 1999, and hundreds of research papers build on it. Hours later, Anthropic published a proof of its own, found by an internal Claude model with no human input. Both labs found their proof on October 16, and both ship it with a check in the proof assistant Lean. Experts are still reviewing it, and nothing changes in practice for now. What matters for companies is the way to check it: AI now delivers research-grade results, and the best ones come with a check any computer can rerun. We did exactly that with Anthropic's proof on a Mac.

What the two labs report

The conjecture concerns a basic problem in computer science. A formula made of yes-no switches has to be set so that every condition holds. Trying every setting doubles the work with each extra switch. Since the 1980s, researchers have pushed that overhead down, most recently to just under 31 percent per switch. The hypothesis by Russell Impagliazzo and Ramamohan Paturi says it can never vanish entirely.

Both papers claim the opposite. OpenAI's paper runs to 67 pages, Anthropic's to 49. Both describe a method whose overhead per switch falls toward zero as the formula grows. According to Anthropic, the model needed 14 million output tokens to get there.

OpenAI released two more results the same day. One proves a 1991 conjecture about how waves focus, which also implies the well-known Kakeya conjecture. The other is an existence proof for quantum chromodynamics, the theory of the strong nuclear force, and touches one of the Millennium Prize Problems in mathematics. Those materials are not public yet. A group led by Nobel laureate David Gross is reviewing them. According to OpenAI's announcement, everything comes from an unreleased model that was given about 4,000 open problems, with an average of three hours of thinking time per result.

The catch

• Nobody has confirmed it independently yet. OpenAI's proof is being reviewed by a group around Impagliazzo, Paturi and Ryan Williams of MIT, and OpenAI is paying for a conference on it. According to TechCrunch, Williams called OpenAI's bulk release from early October a “DDOS attack on mathematicians”.
• Lean checks the proof, not the question. The program confirms that the chain of reasoning has no gaps. Whether the statement in Lean is exactly the intended conjecture is something no machine checks. Anthropic says so itself and keeps the decisive file short for that reason.
• Mistakes happen. On October 7, OpenAI withdrew three manuscripts over a sign error and revised 14 others. According to OpenAI, about 42 percent of the main results are formally checked.
• Useless in practice, say the authors themselves. Anthropic works out how large a formula must be before the method beats plain trial and error.

We reran the check

Anthropic explains how to check the proof yourself. We did that on October 28 on a MacBook Pro with an Apple M4 Max: installed Lean, downloaded the prebuilt mathematics library and had the proof compiled. Downloading the library took 5:36 minutes, compiling and checking the proof 8:54 minutes. Anthropic cites about eight minutes on a server with 24 virtual CPUs. At the end there are two lines: both main theorems rest only on Lean’s three standard axioms. No step was skipped, no assumption hidden.

What this does not show is whether the statement really captures the conjecture. That still takes experts. But the most laborious part of the check is no longer a matter of trust. It is a computation anyone can repeat.

What this means for mid-sized companies

In the short term, nothing. Planning, configuration and verification software keeps working as before. Such tools rely on real formulas having structure, not on the worst case this result is about. Encryption stays as it is too: according to Williams, OpenAI checked and is reasonably confident that no breaks follow from it.

What matters more is what the news says about the tools. Two labs independently overturned an assumption that had been considered safe for 27 years. And both waited until a machine could check the proof. That pattern carries over: result plus a way to check it. For code that means tests, for calculations a cross-check, for designs a simulation or measurement. The more the models deliver, the less people can read by hand. According to Anthropic, even the publicly available Claude Opus 5.5 can derive the refutation from a short sketch. We described what this looks like for software in “Proven, not tested”.

What you should do now

1. Change nothing. No encryption and no planning software needs to change because of this news.
2. Define the check before the task. Decide how an AI result will be checked by machine before you ask for it: tests, cross-checks, limits, simulation.
3. Budget time for review. An AI delivers in hours what experts take weeks to read. Plan your experts for acceptance, not just for creation.
4. Write down one open problem. A tolerance calculation, a planning rule, a measurement error nobody can explain. With a check attached, it makes a good first test for today's models.
5. Wait for the review group's verdict before citing the refutation in proposals or strategy papers.

The mathematics is new, the principle is not: what a machine can check, nobody has to take on faith. If you would like to build the check into a first use case from the start, we are happy to talk.