The Exponential Time Hypothesis Is False
On this page
On 25 October 2026, OpenAI released a preprint arguing that the Exponential Time Hypothesis (ETH) is false. ETH is a central conjecture in computational complexity: it holds that there is no sub-exponential algorithm for SAT and related problems, and it is widely assumed when proving hardness results. If the claim holds, it would overturn a foundational assumption used across algorithms research.
The paper was published as a PDF in OpenAI’s public math repository and accompanied the announcement of three new discoveries in mathematics, computer science, and physics. Because the result touches a deeply entrenched conjecture, the community reaction has been cautious: preprint claims of this magnitude typically require extended verification before being accepted, and complexity theorists have historically treated ETH as a very safe assumption.
Why It Matters
ETH is not merely an esoteric curiosity — it underpins the hardness of many practical problems (SAT, graph problems, and more) and the design of algorithms that assume worst-case exponential barriers. A credible counterexample would force a re-examination of dozens of results. This is also a notable moment for AI-driven research: a frontier model contributing a major complexity-theory claim highlights both the promise and the epistemic risk of machine-generated mathematical results. See AI in Science and Technical Frontiers, Frontier Labs, and Knowledge, Reasoning, and Semantics.
Sources
- OpenAI. The Exponential Time Hypothesis Is False (preprint, 25 Oct 2026). https://github.com/openai/math/blob/main/preprints/The-Exponential-Time-Hypothesis-is-False-October-25-2026/paper.pdf
- OpenAI. Building scientific understanding with academic communities (26 Oct 2026). https://openai.com/index/building-scientific-understanding-with-academic-communities/
Back to Recent Topics · See also Three New Discoveries in Mathematics, Computer Science, and Physics.