OpenAI announced that its artificial intelligence model has found a way to disprove the Exponential Time Hypothesis (ETH), a well-known conjecture in computer science from 1999. This statement caused a stir on Crypto Twitter, where many users mistakenly assumed that “ETH” referred to the Ethereum cryptocurrency. However, the ETH in question is unrelated to Ethereum, its price, or co-founder Vitalik Buterin.
Exponential Time Hypothesis and Computer Science
The Exponential Time Hypothesis is a conjecture proposed by computer scientists Russell Impagliazzo, Ramamohan Paturi, and Francis Zane in 1999. It relates to the computational complexity of solving certain logic puzzles, particularly the 3-SAT problem. This problem involves finding combinations that satisfy a set of rules, typically in groups of three.
ETH has been widely assumed in hundreds of academic papers to establish that certain complex problems in graph theory, computational biology, databases, and geometry cannot be solved quickly. It effectively acts as a map indicating which problems computers are unlikely to solve efficiently.
OpenAI’s research team claims their AI model has produced a deterministic algorithm that counts every satisfying solution for these puzzles in subexponential time, meaning the computational effort grows significantly slower than previously believed possible under the ETH.
“The refutation of the ETH reopens questions about how much faster these tasks could become and may help guide the search for better algorithms,” OpenAI wrote on its official blog.
Mini dictionary: Exponential Time Hypothesis (ETH) is a conjecture in computational complexity theory stating that certain types of logic problems, such as 3-SAT, cannot be solved faster than in exponential time in the worst case. It forms the foundation for many assumptions about problem-solving limits in computer science.
Review and Implications
OpenAI published a 67-page paper on October 17, revised October 25, describing the new algorithm. According to the company, its AI found the disproof on October 16, and the formal proof was verified using the Lean proof assistant software the next day. The research and accompanying proof files are now available on GitHub for scrutiny.
Three computer scientists — ETH proposers Russell Impagliazzo and Ramamohan Paturi, along with MIT’s Ryan Williams — are currently conducting an independent review of OpenAI’s findings. In an open letter, they emphasized that their involvement should not be regarded as a certification of the result. They also stressed the need for independent verification and a thorough understanding that allows others to reconstruct and question the work.
Impagliazzo, Paturi, and Williams wrote, “A result of this significance requires careful, independent scrutiny and an understanding that others can reconstruct, question, and build upon.”
OpenAI noted that while their result is significant in theory, practical benefits may take considerable time to materialize. The paper explicitly states that the breakthrough does not imply every NP problem can now be solved efficiently, leaving the famous P versus NP problem unresolved. In computational theory, P represents problems easily solved by computers, while NP covers problems whose solutions can be efficiently verified.
Anthropic, another AI company, followed with its own announcement. Using its Claude AI model, Anthropic published a paper on October 26 describing a new 3-SAT algorithm that also addresses the ETH problem. However, Anthropic clarified that its results are theoretical and do not currently impact practical problem-solving.
Mini dictionary: Anthropic is an artificial intelligence research company that develops AI models such as Claude. The company focuses on creating advanced, reliable AI systems for complex tasks in science and mathematics.
OpenAI’s Unreleased AI Model and Broader Impact
In a related development, OpenAI released 722 mathematics manuscripts on GitHub, generated by an unreleased internal AI model. According to an OpenAI spokesperson, most were produced from a single prompt to a single AI agent, though some required multiple attempts. The company characterized this as a major step forward in AI-assisted mathematical discovery. Nevertheless, skepticism remains within the mathematics community regarding AI verification and reproducibility.
OpenAI has contributed $5 million to the Simons Foundation, an American philanthropic organization focused on advancing research in mathematics and the sciences. This funding will support workshops, conferences, and special programs aimed at evaluating and building upon AI-generated results in mathematics.
The entire episode highlights the growing interest of leading AI companies, including Anthropic and OpenAI, in addressing complex, unresolved problems in mathematics and computer science through advanced artificial intelligence models.
| Institution | Algorithm/Model | Key Announcement Date | Claimed Achievement |
|---|---|---|---|
| OpenAI | Unreleased internal AI model | October 17, 2023 | Disproved Exponential Time Hypothesis, published 722 manuscripts |
| Anthropic | Claude | October 26, 2023 | Discovered new 3-SAT algorithm, theoretical results |
