OpenAI has put out a mathematics paper whose title states that the Exponential Time Hypothesis is false. If the proof holds, it removes one of the working assumptions of modern theoretical computer science: that the hardest logic puzzles of a standard kind cannot be solved much faster than by trying every possibility. A great many published hardness results lean on this hypothesis, so a confirmed refutation would force a rethink across the field.
The paper, dated 17 October and revised on 25 October 2026, is posted in OpenAI's public math repository on GitHub and credited to OpenAI alone, with no individual authors. The repository says its manuscripts were produced by an unnamed internal OpenAI model and should be treated as raw research data rather than finished papers. Across more than 60 pages, its main theorem gives a deterministic algorithm that counts every satisfying assignment of a k-CNF formula, a logic formula built from clauses of at most k terms, for any fixed k of 2 or more. The running time grows roughly as 2 raised to n divided by the square root of log n, where n is the number of variables, and the memory use stays polynomial. That is slower than polynomial time but faster than any 2 to the power of a constant times n, which is exactly what the hypothesis rules out. Counting solutions is harder than deciding whether one exists, so the result also refutes the counting version of the hypothesis and, the paper argues, its stronger cousins.
The method is algebraic. In our reading of the introduction, it splits the variables into groups, turns the formula into low-degree polynomial equations, and counts their common zeros using interpolation and fast summation, building on earlier split-and-list and inclusion-exclusion techniques. The paper lists consequences: subexponential exact counting of graph colourings, independent sets and perfect matchings, and approximation schemes for Max-k-SAT. It is careful to say this does not give fast algorithms for every NP problem, because time bounds of this shape do not carry over through ordinary reductions.
The context makes caution essential. The previous best exact counters for 3-SAT still ran in clearly exponential time, and decades of work, including the PPSZ algorithm and its refinements, pushed the base of the exponent down only slowly. One of the paper's corollaries also relies on another OpenAI preprint, The Unique Games Theorem, from September, which is itself unreviewed.
Nothing here has been peer reviewed, OpenAI's own repository warns that results without a Lean formal proof could contain errors, and we have not seen published responses from complexity theorists. Results of this size have been announced and withdrawn before, often because of a gap that only surfaced after specialists worked through every lemma. The right stance for now is interest without belief: the paper is detailed enough for specialists to check step by step, and their verdict will settle the question faster than any commentary.