OpenAI says its AI refuted the Exponential Time Hypothesis. The checking has only started

On 26 October OpenAI announced that its internal models had produced three research results, among them a disproof of the Exponential Time Hypothesis, Unite.AI reports. The preprint is titled "The Exponential Time Hypothesis is False" and names OpenAI as its only author. Unite.AI credits the hypothesis to Russell Impagliazzo and Ramamohan Paturi of UC San Diego, who proposed it with Francis Zane, and reports OpenAI's own description: a widely believed conjecture that hundreds of papers have used to derive hardness results in graph theory, computational biology, databases and computational geometry. The mathematics is for specialists. The checking is the part every team that relies on AI output should follow.

What the paper claims

OpenAI posted the preprint's LaTeX source in its public openai/math repository. Its abstract makes one claim: "We give a deterministic algorithm for exactly counting the satisfying assignments of an arbitrary k-CNF formula." In plain terms, the algorithm takes a logic puzzle of the kind computer science treats as the textbook hard case and counts every way to solve it.

The hypothesis, in the abstract's words, "postulates that deciding 3-SAT on n variables requires" exponential time in the worst case: time that multiplies at a fixed rate with every variable added. The claimed algorithm still slows down sharply as formulas grow, but more slowly than any fixed exponential rate. Computer scientists call that subexponential, and it is exactly what the hypothesis ruled out.

The paper draws its own limits. Bounds of this kind "do not transfer under general polynomial-time reductions", it says, so "our result does not imply that general NP problems admit subexponential time algorithms." It does claim faster algorithms for counting graph colourings and perfect matchings. Nothing in the abstract, or in OpenAI's announcement as Unite.AI reports it, mentions encryption. On practical use, OpenAI said that turning the theory into real improvements "will require significant further research", according to Unite.AI.

What the Lean proof covers

Unite.AI reports that the model produced its natural-language disproof on 16 October and that OpenAI dates the Lean formalisation to 17 October. Lean is a proof assistant: it checks every step of a formal proof mechanically. The LaTeX source is dated "17 October 2026, revised 25 October 2026".

That order matters. OpenAI's scope note for the Lean proof says the 25 October manuscript gives "the sharper time bound". The bound Lean proves is weaker, though Unite.AI, reading the same note, reports that it is still subexponential. If the formal statement means what the paper means, the Lean proof alone carries the refutation.

That "if" is the work left. The scope note lists one formalised result, "Exact counting and SAT on canonical inputs in subexponential time and polynomial space", stated in a file called SubexponentialSAT.lean. Lean confirms that this statement follows from its definitions. It cannot confirm that those definitions, from the "canonically encoded" input to the machine that does the counting, match what the field means by the hypothesis. People do that comparison. The colourings and matchings results are not on the scope note's list. OpenAI's repository README is candid about the wider collection: it "includes results at different stages of verification", and "some of the unformalized results could have issues."

Who is checking

Unite.AI names the group that will verify and shepherd the result: Impagliazzo and Paturi, and Ryan Williams of MIT, who OpenAI noted has refuted strong versions of the hypothesis. Two of the three named leads proposed the conjecture this result would overturn. OpenAI agreed to the group's request that all raw data behind the result be made public for independent verification, and to fund a conference on what the work means for the field. The group has invited the community to help organise an open examination.

The claim stands if that examination finds the formal statement faithful to the hypothesis. It falls on a mismatch in the definitions, or on an error in the parts Lean does not reach.

The same split is arriving in ordinary work. OpenAI's README counts 721 manuscripts in 373 families in this one repository, more output than any team reads closely. A mechanical check covers what can be formalised: tests, totals, a proof assistant. A person with standing decides whether the checked thing is the thing that was claimed. AI does the routine work. You do the thinking, and the signature under the verdict is yours.

Your Next Move

• When an AI result reaches you as "proven" or "verified", ask what was checked: the formal statement, or the headline written about it.
• Read the source's own scope note before the coverage. Here, OpenAI's note on the Lean proof says more precisely what was proven than the announcement does.
• Quote this as OpenAI's claim until the Impagliazzo, Paturi and Williams group reports, and write down the date you last checked.