OpenAI announced on October 26, 2026, that an internal system had produced a result the company says refutes the Exponential Time Hypothesis (ETH), a conjecture about the difficulty of Boolean satisfiability problems. OpenAI dates the natural-language result to October 16 and its formalization in Lean to October 17.
What OpenAI says its system found
OpenAI says the result concerns counting satisfying assignments for Boolean formulas. The company announced that a group led by Russell Impagliazzo, Ramamohan Paturi and Ryan Williams would examine and explain the work.
ETH is a conjecture that 3-SAT, a Boolean satisfiability problem, cannot be solved in subexponential time in the worst case. OpenAI says ETH has underpinned conditional hardness results in hundreds of papers across fields including graph theory, computational biology, databases and computational geometry.
What the Lean theorem covers
OpenAI’s Lean scope documentation describes a deterministic algorithm that exactly counts satisfying assignments for canonically encoded k-CNF formulas, with k fixed at 2 or greater. Here, “exactly counts” means calculating the number of assignments that satisfy the formula, rather than only deciding whether a solution exists.
For n variables and an encoding with bit length L, the documented runtime is (L+1)^{O_k(1)} 2^{O_k(n(log log n)^2/√log n)}. The same scope statement says the machine visits at most (L+1)^{O_k(1)} tape cells in total.
Why the manuscript bounds are separate
The Lean scope documentation separately attributes a sharper runtime, (n+m)^{O_k(1)} 2^{O_k(n log log n/√log n)}, to the October 25 manuscript. Here, m is the number of clauses. For formulas with m ≤ Dn, where D is a fixed positive constant, the documentation attributes this further bound to the manuscript: (n+m)^{O_{k,D}(1)} 2^{O_{k,D}(n/√log n)}.
Those expressions are manuscript bounds, distinct from the runtime stated for the Lean theorem. Keeping them separate clarifies what the formalized scope says and which stronger runtimes the documentation attributes to the accompanying manuscript.
What the claim means for ETH and software
OpenAI’s announcement concerns ETH; it does not report a solution to P versus NP. Nor does a subexponential theoretical runtime establish an immediate speedup for practical software. OpenAI says translating theoretical advances into practical improvements will require significant further research.
Adem B10’s video uses a simplified switch-puzzle example to illustrate solution counting. The puzzle is an explanatory illustration, not OpenAI’s algorithm.
On October 28, 2026, ExplainX reported that independent confirmation had not been reported by that date.
