Malhar Ujawane

Inspiration

Inspiration·

OpenAI says its models proved the Exponential Time Hypothesis false

OpenAI released an AI-written disproof of the Exponential Time Hypothesis with a Lean proof, shepherded by the researchers who proposed ETH.

OpenAI’s Working with academic communities to build scientific understanding (October 26, 2026) announces three results its internal models produced: a proof of Sogge’s local smoothing conjecture in every dimension (which also settles Kakeya and Stein’s restriction conjecture), an existence proof for QCD and pure Yang-Mills in four dimensions, and a disproof of the Exponential Time Hypothesis. The Hacker News thread is at 1,133 points as of October 28, and the ETH paper got its own front-page thread.

ETH is the conjecture that 3-SAT can’t be solved in time that is subexponential in the number of variables. A lot of “this problem has no fast algorithm” results are conditional on it. OpenAI’s framing:

The ETH has been widely believed to be true, and has been used in hundreds of papers to derive conditional computational hardness results across a wide variety of fields including graph theory, computational biology, databases, computational geometry, and more.

I can’t check a complexity proof myself, so I’m watching the verification process. Three things in the post do the work there. There’s a Lean formalization, published next to the natural language paper in openai/math. The shepherding group is led by Russell Impagliazzo and Ramamohan Paturi, who proposed ETH in the first place, plus Ryan Williams. And OpenAI says it isn’t seeking academic credit for the discoveries.

The Lean part is what makes this different from a press release. I linked a piece last week on LLMs making formal verification feasible at scale, and this is that idea at full size: a machine-checked proof plus the people best placed to read the formal statement and confirm it says what ETH says. A Lean proof only proves the statement that was formalized, so that check matters.

For builders, OpenAI is clear this doesn’t mean faster SAT solvers next quarter: “Finding such algorithms, and turning theoretical advances into practical improvements, will require significant further research.” The preprints/ folder in the repo has 751 entries as of October 28. That’s the part I keep thinking about. The bottleneck has moved from producing results to understanding and checking them, which is the same problem I have with agent-written pull requests, at a much smaller scale.

Get new posts in your inbox

© 2026 Malhar Ujawane. Built with Astro.