# OpenAI says an AI system disproved the Exponential Time Hypothesis, and the conjecture's original authors are now reviewing the Lean proof

The claimed algorithm counts 3-SAT solutions in barely subexponential time. That leaves the problems behind blockchain signatures untouched but removes a lower bound that hundreds of complexity results relied on.

- Published: 2026-10-27T05:37:50.880Z
- Canonical: https://polylog.news/crypto/2026-10-27/openai-says-an-ai-system-disproved-the-exponential-time-hypo
- Publisher: Polylog (Crypto desk)
- Section: tech
- Sources: [Hacker News (OpenAI preprint)](https://github.com/openai/math/blob/main/preprints/The-Exponential-Time-Hypothesis-is-False-October-25-2026/paper.pdf), [Hacker News (OpenAI announcement)](https://openai.com/index/building-scientific-understanding-with-academic-communities/), [Ethereum Research](https://ethresear.ch/t/lean-verification-of-eip-7002-system-call-success-and-fifo-requests/26180)

On October 26, OpenAI [announced](https://openai.com/index/building-scientific-understanding-with-academic-communities/) that one of its systems had refuted the Exponential Time Hypothesis (ETH). Since 1999, the ETH has served as the standard assumption that 3-SAT, a basic logic-satisfiability problem, cannot be solved in subexponential time. According to [reporting on the announcement](https://ai-tldr.dev/releases/openai-eth-false-kakeya-results/), the model produced a natural-language disproof on October 16, and the proof was formalized in the Lean proof assistant on October 17. OpenAI announced two other results at the same time, one in harmonic analysis and one in quantum field theory.

The [preprint](https://github.com/openai/math/blob/main/preprints/The-Exponential-Time-Hypothesis-is-False-October-25-2026/paper.pdf) describes a deterministic algorithm. It counts the exact number of satisfying assignments of fixed-width conjunctive normal form formulas (a standard way of structuring logical statements in satisfiability problems) and uses only polynomial memory. The Lean statement gives a running time of 2 raised to O(n·(log log n)²/√log n). That is far slower than polynomial time, but it beats every 2^(cn) bound that the ETH says 3-SAT requires, [as summarized by FourWeekMBA](https://fourweekmba.com/ai-openai-says-its-ai-refuted-the-exponential-time-hypothesis/). Russell Impagliazzo and Ramamohan Paturi of the University of California, San Diego, two of the three authors who proposed the ETH, will verify the work together with Ryan Williams of the Massachusetts Institute of Technology (MIT). Independent academic confirmation has not yet been published.

For cryptography, the precise scope matters. Elliptic-curve signatures, hash functions and lattice schemes depend on the hardness of specific problems, not on the ETH, and disproving the ETH does not show that P equals NP. The savings in the exponent grow extremely slowly with problem size. The damage falls instead on fine-grained complexity theory. Many conditional lower bounds in that field begin with "assuming ETH," and those results now need new foundations. OpenAI itself says that turning the result into practical speedups "will require significant further research."

The same machine-checked method is reaching protocol code. On Ethereum Research, a contributor published a [Lean verification of EIP-7002](https://ethresear.ch/t/lean-verification-of-eip-7002-system-call-success-and-fifo-requests/26180), the hand-written 504-byte contract at 0x00000961Ef480Eb55e80D19ad83579A64c007002. Since the Prague upgrade, validator exits and partial withdrawals requested from the execution layer pass through this contract. The proof shows that the per-block system call succeeds and that requests leave the contract in first-in, first-out order.

## What this means

The direct risk to deployed cryptography is close to zero. The change is in who can now attack mathematical assumptions and how fast. A machine-checked refutation of a 27-year-old conjecture shows that AI systems can now produce new, verifiable results in complexity theory. The same capability can be pointed at the specific problems behind signatures and proof systems. The precedent is SIKE, a post-quantum candidate that a classical attack broke on a single laptop in 2022. In that case the construction failed, and the general theory survived. Public reactions are likely to split between two overstated claims, that cryptography is broken or that this is an irrelevant academic result. Neither claim addresses the real issue, which is the rate at which underlying assumptions are now being tested. The likelier outcome over the next several months is a rise in AI-assisted cryptanalysis papers and formal-verification work aimed at production code such as EIP-7002. Protocol teams with formal proofs will gain credibility, and teams relying on informal audits will lose it. The desk's view depends on the Impagliazzo, Paturi and Williams review confirming the proof. If the reviewers find a gap in the Lean formalization, this result would illustrate the risk of trusting unverified AI claims rather than serve as evidence of AI capability.

## What to watch

- The verdict from the review group at UC San Diego and MIT. A confirmation changes how researchers treat AI-generated proofs, and a gap in the formalization would set that back.
- Whether AI-assisted attacks on specific cryptographic problems, such as lattice parameters or the arithmetic behind proof systems, appear on the IACR ePrint archive in the coming months. Those problems are where deployed crypto is actually exposed.
- Whether Ethereum client teams adopt Lean proofs for more system contracts before the next hard fork. Doing so would turn formal verification from research into release practice.