OpenAI announced on October 26, 2026, that an internal system had refuted the Exponential Time Hypothesis (ETH), a conjecture about the difficulty of Boolean formula satisfiability. That is OpenAI’s claim: the company says its system produced a natural-language result on October 16, formalized it in Lean on October 17, and made the write-up and Lean proof public. OpenAI’s announcement also named an external group to shepherd and explain the result.
ETH has been used as a premise in hundreds of papers deriving conditional results about computational hardness, according to OpenAI. If the claim withstands scrutiny, researchers could revisit work that depends on that assumption.
If the claim holds up, its reach could extend beyond one algorithm to research built on ETH.
What OpenAI says it did
OpenAI says its system first produced a natural-language disproof, then the result was formalized in Lean, a proof assistant used to express mathematical statements in a form that can be checked. The company said both the write-up and the Lean proof were publicly available with its October 26 announcement.
OpenAI also announced an external collaboration led by Russell Impagliazzo, Ramamohan Paturi, and Ryan Williams to shepherd and explain the computer-science result. OpenAI said the group’s conclusions would be its own.
E8 Holographic Framework’s video commentary raises a separate technical question: whether checking a proof’s formal steps also accounts for the bit-level cost of carrying out an algorithm. The creator argues that the size of intermediate numbers matters to that runtime calculation. This is the creator’s critique, distinct from the external collaboration OpenAI announced.
ETH is not P vs. NP
ETH concerns the computational difficulty of Boolean formula satisfiability. The New York Times reported that Russell Impagliazzo, Ramamohan Paturi, and Francis Zane proposed the hypothesis in 1998. Its report on the announcement also says the broader P vs. NP problem remains unsolved. OpenAI’s announcement concerns ETH; it does not claim to resolve P vs. NP.
What the claim could mean for computing
A theoretical result can affect assumptions researchers use even before it changes practical computing. OpenAI says translating theoretical advances into practical improvements will require significant further research.
