OpenAI releases claimed ETH refutation for independent review

OpenAI released an AI-produced manuscript and Lean proof on October 26 claiming to refute the Exponential Time Hypothesis, or ETH. Two of the hypothesis's original proposers, Russell Impagliazzo and Ramamohan Paturi, will lead an independent examination with MIT's Ryan Williams.

The three researchers say their involvement is no certification of correctness. Their open letter calls for checking the argument and developing explanations others can reconstruct and challenge. Researchers relying on ETH now have material for reassessing that assumption. OpenAI says hundreds of papers have used ETH for conditional hardness results in areas including graph theory, computational biology and databases.

ETH concerns the worst-case time needed to decide whether a 3-SAT formula has a satisfying true-or-false assignment. The manuscript claims a deterministic algorithm that exactly counts satisfying assignments for formulas with a fixed bound on clause width, using subexponential time and polynomial space.

Checking whether the count exceeds zero also decides satisfiability. The paper explicitly warns that its time guarantee does not transfer through general polynomial-time reductions to every NP problem. Its scope fixes clause width as the variable count grows. The manuscript is dated October 17, with a revision dated October 25. This time bound alone does not establish P equals NP.

The manuscript and formalization specify different bounds

The published target-statement file specifies exact counting for canonically encoded formulas with fixed clause width of at least two. It separates the number of variables from the input's bit length and places a polynomial bound on space. This specifies the inputs and computational model targeted by the formalization.

That document states a weaker time bound than the sharper one in the October 25 manuscript. Both are subexponential in the variable count, but the improved manuscript bound has a different stated scope from the formalized one. The document separately records manuscript bounds for general clause counts and for clause counts proportional to variables.

Lean's Comparator documentation describes checking that a submitted proof establishes the same statement as the target, uses permitted axioms, and is accepted by the Lean kernel. Definitions appearing in the statement are also compared. Reading how that formal statement relates to the hypothesis being discussed remains part of examining the claim.

OpenAI's repository describes its contents as manuscripts and proof artifacts from an unnamed internal model. It presents the collection as raw research data at different stages of verification. Its version policy preserves previous public editions when corrections appear, allowing the ETH manuscript and its scope documentation to be tracked individually.

OpenAI says it obtained the natural-language ETH result on October 16 and formalized it the next day. External participation is voluntary and unpaid, without nondisclosure agreements. Williams separately confirmed that the group requested immediate release of PDFs and Lean source, and said its ongoing findings would be shared with the community. OpenAI agreed to release the material and fund a conference on implications for the field.

The researchers propose sharing questions, gaps, corrections and verified steps while retaining independent approaches and criticism. Explanations, simplified proofs and seminars are among the resources they discuss. The letter's appendix seeks views on the desirability, format and timing of a proposed virtual meeting before the end of 2026; it specifies no meeting date.