Did OpenAI Bots Disprove The Exponential Time Hypothesis? Experts Are Checking

A belief that hundreds of computer science papers lean on may be wrong, and the claim comes from an AI model. OpenAI says one of its internal systems has disproved the Exponential Time Hypothesis, a decades-old idea about how quickly computers can crack certain logic puzzles. If the result survives expert scrutiny, a long list of hardness proofs would lose a key assumption.

OpenAI announced the claim on October 26, 2026. According to the company, its model produced the disproof on October 16, and a proof-checking program called Lean confirmed the argument the next day. In its own words, “our system has recently proved that the ETH is false”.

Skepticism is built into the rollout. OpenAI calls its manuscripts “raw research data” and has asked two of the scientists who proposed the hypothesis, along with an MIT researcher, to lead the checking. A second AI lab has since posted a rival claim, and nobody has declared the matter settled.

Why the Exponential Time Hypothesis matters to computer science

At issue is a family of puzzles called Boolean satisfiability. In one version, known as 3-SAT, a long list of yes-or-no choices must be set so that every demand on a list is met, with each demand naming three of the choices and satisfied if at least one goes the right way. Checking a proposed answer is quick. Finding one seems to demand a hunt through a staggering number of combinations. Testing every possibility doubles the work with each added choice, and even the cleverest known methods still multiply the work by a fixed amount for each one.

Russell Impagliazzo and Ramamohan Paturi, both at UC San Diego, proposed the Exponential Time Hypothesis with Francis Zane, in work published in 2001. It bets that no algorithm can ever shed that fixed multiplier entirely. Because the bet has gone unbroken for so long, researchers have treated it as a foundation. OpenAI says hundreds of papers have leaned on the idea to argue that certain tasks, from graph theory and computational biology to databases and geometry, cannot be sped up much. The paper itself says some of those hardness results also follow from weaker assumptions that may still hold.

OpenAI’s Exponential Time Hypothesis claim, in plain terms

Computer scientist Lance Fortnow summarized the announcement on X: OpenAI claims to solve 3SAT, and even to count the number of solutions, in “2^{o(n)}” time. In everyday terms, that means work growing more slowly than any fixed exponential, which would break the hypothesis. The manuscript says the same algorithm also refutes the Strong Exponential Time Hypothesis, a bolder cousin of the original idea.

Slower growth does not mean fast. OpenAI itself says that finding better algorithms and turning theory into practical improvements will take much more research. Nor would the result settle the famous P versus NP question, which OpenAI describes as deeply related to the puzzle. The paper says it does not show that general NP problems have subexponential algorithms, and Fortnow wrote in a later post that the claimed refutation “doesn’t reduce the running times of NP problems in general” and added, “We still have no approach to settling P v NP.”

Who is checking the Exponential Time Hypothesis claim

Impagliazzo, Paturi, and Ryan Williams of MIT lead the review. Williams posted that no one in the group signed a nondisclosure agreement or is being compensated, The Next Web reported. OpenAI agreed to release all raw data and fund a conference where the community can examine the claim.

Even the reviewers have been blunt about their role. In an open letter, they wrote, “Our involvement should not be taken as certification of the claim.” They added that a correct result would change an important part of theoretical computer science, and that something this weighty calls for independent scrutiny. A further worry in the letter is credit. If AI finds results first, the authors say, recognition could flow to whoever publishes earliest or owns the strongest tools, leaving the people who verify and explain a result with less, according to The Next Web.

One built-in caution involves the proof checker itself. Lean confirms that each logical step in a formal proof holds, but experts still must judge whether the formal statement matches the claim made in the paper.

Open questions as a second lab joins the debate

On the same day, Anthropic posted its own paper, “A 2^o(n) Time Algorithm for 3-SAT,” credited to an internal Claude model, Decrypt reported. Anthropic’s repository states, “the result is purely asymptotic and says nothing about solving formulas in practice.” Neither lab’s claim has been independently confirmed.

For now, the Exponential Time Hypothesis is a hypothesis under challenge, not a discarded one. Independent reviewers, not the labs that posted the papers, will weigh in on which way it falls.

---