OpenAI says its AI has refuted the Exponential Time Hypothesis

OpenAI said on Monday 26 October 2026 that one of its internal AI models produced a 67-page paper claiming to refute the Exponential Time Hypothesis (ETH), an assumption OpenAI says has been used in hundreds of papers. The claim has not been peer reviewed, and the researchers OpenAI has asked to examine it say their involvement "should not be taken as certification of the claim".

What ETH and SETH say

Take a long list of "either/or" conditions on n yes-or-no switches. Is there a setting of the switches that satisfies every condition at once? That is the 3-SAT problem when each condition involves at most three switches. Brute force means trying all 2 to the power n settings.

ETH, set out by Russell Impagliazzo and Ramamohan Paturi in "On the Complexity of k-SAT" (Journal of Computer and System Sciences, 2001), says there is no fundamentally better shortcut: the cost must still grow exponentially. OpenAI's paper states it as the postulate that "deciding 3-SAT on n variables requires 2^Ω(n) time in the worst case". The Strong Exponential Time Hypothesis (SETH) goes further, predicting that as the conditions get longer the best possible method gets ever closer to brute force.

What the paper claims

The paper, titled "The Exponential Time Hypothesis is False" and dated 17 October 2026, revised 25 October, describes a deterministic algorithm for counting, not just finding, the satisfying settings of a k-CNF formula (the general version of the problem above). Its abstract says that for every fixed k ≥ 2, on a formula with n variables and m clauses, the algorithm uses polynomial space and runs in time (n+m)^O_k(1) · 2^(n/(log n)^(1/2+o(1))). That is slower than any polynomial but, the paper argues, below exponential, which it says refutes ETH. It says the result also refutes SETH and related hypotheses.

The paper also says its result "does not imply that general NP problems admit subexponential time algorithms", so, on our reading, it does not settle P versus NP.

How it was produced

The paper's sole listed author is "OpenAI". A search of its text found no statement on AI involvement; that is in the surrounding material. The repository's README says "The vast majority of results were obtained with the same procedure using an unreleased internal OpenAI model", and that each result used on average "three hours of ChatGPT Pro thinking compute"; it does not give a figure for this paper. It also says the manuscripts are "best understood as a form of raw research data, rather than polished academic papers". OpenAI's announcement says: "Our AI found its natural language disproof for the ETH on October 16th, 2026 and then subsequently we formalized the result in Lean on October 17th, 2026".

Verification and the academic process

OpenAI says "our system has recently proved that the ETH is false, a result that was subsequently verified in Lean", the proof-checking language. Its Lean notes state a formally proved time bound slightly weaker than the manuscript's sharpest one. On our reading, a machine check confirms the formal statement; whether that statement captures the paper's claim is still for experts to judge.

OpenAI says the work "will be verified and shepherded by a group led by Russell Impagliazzo (UC San Diego), Ramamohan Paturi (UC San Diego), and Ryan Williams (MIT)", and that it agreed to the group's request that it commit to funding a conference. It says participants will not be asked to sign non-disclosure agreements and that it does "not seek academic credit". In an open letter, the three researchers write: "Our involvement should not be taken as certification of the claim. A result of this significance requires careful, independent scrutiny".

Reaction

The Verge reported that a panel of maths advisers OpenAI assembled had said "we recommend that AI companies do not adopt" the practice of giving chosen researchers first access.

On Hacker News, one commenter wrote: "I was highly critical of their approach with the earlier mathematical publications, but this is much improved." Another said "I think OpenAI deserve credit for adjusting their approach after the last math drop." A sceptic wrote: "Treating every result from the AI like a gift from god is getting tiring." A commenter describing themselves as a SAT-solving expert said there were "No immediate applications (the results in the paper are "galactic")", and that "The main question is whether some ideas here will snowball into other ideas, one of which could eventually be very practical." None of these commenters is identified.

Kakeya and QCD

OpenAI's announcement also claims a proof of the local smoothing conjecture in every dimension, which OpenAI says resolves the Kakeya conjecture, and an existence proof for quantum chromodynamics, whose materials have not been released. Both are also unreviewed.

Why it matters

The researchers' letter says: "If the claim is correct, it will change an important part of theoretical computer science." OpenAI says turning the result into practical improvements "will require significant further research". On our reading, the first test is the independent check now under way.