Mentioned in This Article
1. What Did OpenAI Claim About the Exponential Time Hypothesis?
OpenAI has published a 67-page paper, hosted on GitHub, asserting that its AI system found a way around the Exponential Time Hypothesis, a computer-science conjecture dating to 1999. The paper is dated October 17 and was revised on October 25. The researchers who originally proposed the hypothesis are now checking the work, and the claim remains under independent review.
The announcement drew a wave of jokes from crypto users, because the abbreviation for the hypothesis, ETH, is also the ticker of Ether. One user, Takumi, joked on X that algorithmic traders had crushed ETH. Andrew Jiang quipped that Vitalik Buterin had been quiet since the news. In fact, the hypothesis has nothing to do with Ethereum, its price or its co-founder.
The confusion is a coincidence of acronyms, but the underlying story is a serious one in theoretical computer science, where a result of this kind would ripple through hundreds of published papers.
2. What Is the Exponential Time Hypothesis?
The Exponential Time Hypothesis is a conjecture about how fast computers can solve a certain type of logic puzzle. Russell Impagliazzo and Ramamohan Paturi proposed it together with Francis Zane. It states that 3-SAT, a problem that asks whether a set of true-or-false variables can be assigned values to satisfy a list of conditions, cannot be solved much faster than by trying every possible combination.
Researchers have treated the statement as a working assumption. Hundreds of papers rely on it to establish limits on what algorithms can achieve in areas such as graph theory, computational biology, databases and geometry, according to OpenAI. If the assumption fails, those results would need to be re-examined, because many of them show that a problem is hard by proving that a fast solution would break the hypothesis.
One way to picture it is as a map of problems that computers probably cannot solve quickly. OpenAI says its model has redrawn part of that map. In a blog post, the company said the refutation reopens questions about how much faster these tasks could become and may guide the search for better algorithms.
To see why the problem is considered hard, consider a formula with 100 variables, each of which can be true or false. The number of possible assignments is two multiplied by itself 100 times, a figure far beyond what any computer could check one by one. The hypothesis says that, for 3-SAT, there is no shortcut that avoids this explosive growth in a fundamental way. Each added variable roughly doubles the work.
A subexponential algorithm is one whose running time grows more slowly than that kind of doubling. It would still be demanding for large inputs, but the curve would bend away from the worst case that the hypothesis predicts. The notation 2^o(n) in the title of the rival paper expresses exactly that idea.
3. How Does the Claimed Disproof Work?
The paper describes a deterministic algorithm, meaning one that uses no randomness, that counts all of the satisfying assignments of a 3-SAT formula in subexponential time. Counting is a harder task than deciding whether at least one solution exists, so a fast counting method also implies a fast answer to the easier question.
OpenAI says its AI system found the disproof on October 16 and that the argument was formalized in Lean on October 17. Lean is software that mechanically checks logical proofs, step by step, and it is meant to remove the risk of a subtle human error going unnoticed. Both the paper and the formal files are available on GitHub.
The release follows another from earlier in the month, when the company published 722 mathematics manuscripts. Only 162 of those included a main result that had been checked by computer, which gives a sense of how varied the verification status of AI-produced work remains.
Formal verification deserves attention in this context. A written proof, however long, depends on referees reading each step and catching errors, and long arguments have contained mistakes that survived for years. A Lean file, by contrast, is accepted only if every inference passes the software's checker. The remaining risk shifts to whether the formal statement matches what the authors say they proved, which is why specialists still need to read the definitions.
The two dates in the timeline show how compressed the process was. According to OpenAI, the model found the argument on October 16 and the formal version existed the next day. A human research team would usually take far longer to move from an idea to a machine-checked proof.
The difference between deciding and counting also deserves a sentence of explanation. Deciding asks only whether a satisfying assignment exists. Counting asks how many there are, which can require tracking every way the conditions might be met. Because a count of zero means no solution exists, an algorithm that counts quickly answers the yes-or-no question as a by-product, and that is the sense in which the paper's result is stronger than a method that merely decides.
4. Who Is Checking the Result?
Impagliazzo and Paturi are leading an independent review together with Ryan Williams of the Massachusetts Institute of Technology. In an open letter, the three said their involvement should not be read as certification of the result. They called instead for careful, independent scrutiny from the wider research community.
OpenAI says the participants signed no nondisclosure agreements and worked without pay. The company has also agreed to publish all of the raw data and to fund a conference on the result, so that researchers can examine the argument in public.
Separately, OpenAI is contributing $5 million to the Simons Foundation. The money will pay for workshops, conferences and programs through which researchers can examine and build on results produced by AI systems.
For the crypto audience that noticed the story because of the ticker, the practical link is indirect. Much of cryptography rests on assumptions that certain problems are hard, but those assumptions concern different problems from 3-SAT counting, and nothing in OpenAI's statement says that any widely used cryptographic system is affected.
5. Does This Settle P Versus NP?
No. OpenAI states that practical gains are far off and would require significant further research. The paper does not show that every problem in the class known as NP can be solved in subexponential time, so the famous P versus NP question remains open.
The distinction is easiest to see through the definitions. P covers problems that a computer can solve efficiently. NP covers problems whose proposed solutions can be checked efficiently. The P versus NP question asks whether the two groups are in fact the same. A faster algorithm for 3-SAT counting weakens one specific assumption about how hard certain problems are, but it does not collapse the broader divide.
That caution matters for readers who see the headline and assume the result has immediate consequences for cryptography or everyday computing. By the company's own account, it does not, at least not yet.
Open questions remain about independence and credit. A result from a single laboratory can be examined by outside specialists, but two nearly simultaneous claims on the same problem complicate the picture, since reviewers must judge each argument on its own merits. The open letter's insistence that its authors are not certifying the work signals that the field intends to proceed carefully, whatever the competitive pressure.
6. How Has Anthropic Responded?
A rival result appeared quickly. Anthropic posted a paper credited to its Claude model, titled "A 2^o(n) Time Algorithm for 3-SAT," dated October 26. The accompanying repository, which also addresses the Exponential Time Hypothesis, says an internal research Claude model found the algorithm. It adds that the result is purely asymptotic and does not help solve real formulas in practice.
The timing has led some commentators to describe the episode as part of a contest between AI labs over mathematics. Claude had already formalized Fermat's Last Theorem in Lean in September. In that same month, the mathematician Terence Tao warned that rumors of a research project can set off a wave of AI effort to solve the same problem before the original team finishes.
Whether the two claims are independent or related is a matter for the reviewers. Each rests on the same underlying question, and each will face the same standard of scrutiny from specialists in the field.
For observers outside theoretical computer science, the episode is a reminder of how acronyms can mislead. The hypothesis that drew attention shares three letters with the second-largest cryptocurrency, but the two subjects have no technical connection. Anyone looking for a market effect in a paper about algorithm running times is unlikely to find one, and the jokes about trading desks and Vitalik Buterin were just that.
7. What Happens Next?
The immediate step is the independent review led by Impagliazzo, Paturi and Williams, along with the conference OpenAI has promised to fund.
If the review confirms the algorithm, researchers would have to revisit the many results that treat the hypothesis as settled. If it finds an error, the Lean formalization would provide a precise record of where the argument fails. Either outcome would test how the community evaluates proofs that originate from AI systems, a question that now extends across several laboratories.