OpenAI says its models have refuted the Exponential Time Hypothesis

The Exponential Time Hypothesis, proposed by Russell Impagliazzo, Ramamohan Paturi and Francis Zane, says that deciding 3-SAT on \(n\) variables needs time \(2^{\Omega(n)}\) in the worst case. It has been the assumption behind hundreds of conditional hardness results in graph algorithms, computational biology, databases and geometry. On 26 October OpenAI published a paper, dated 17 October and revised on 25 October, that claims to refute it.

The main theorem gives, for each fixed \(k \ge 2\), a deterministic algorithm that computes the number of satisfying assignments of a \(k\)-CNF with \(n\) variables and \(m\) clauses in \((n+m)^{O_k(1)}\, 2^{O_k(n \log\log n/\sqrt{\log n})}\) bit operations and polynomial space. For sparse formulas with \(m \le Dn\) the exponent improves to \(O(n/\sqrt{\log n})\). The method reduces counting for \(k\)-SAT to counting common zeros of sparse polynomial equations, built from low-degree replacement forms and shared linear summaries. A corollary uses Hoeffding’s inequality and a union bound over all \(2^n\) assignments to give subexponential approximation schemes for Max-\(k\)-SAT.

OpenAI says the model wrote the disproof on 16 October and that it was formalised in Lean the next day. The public formalisation proves the weaker bound \(2^{O_k(n(\log\log n)^2/\sqrt{\log n})}\). Impagliazzo and Paturi of UC San Diego and Ryan Williams of MIT will lead a group to verify and explain the result, and asked that all raw data be made public. The paper notes that bounds of the form \(2^{o(n)}\) do not carry over to every NP problem under general polynomial-time reductions.