OpenAI says its AI disproved the Exponential Time Hypothesis
OpenAI announced on October 26, 2026 that its internal models produced three results, including a deterministic algorithm that counts satisfying assignments of k-CNF formulas and thereby refutes the Exponential Time Hypothesis, with the proof formalized in Lean and a working group led by Russell Impagliazzo, Ramamohan Paturi and Ryan Williams set to verify it. The paper's gains are asymptotic and very slow: with all hidden constants set to 1, the general bound only beats the best known 3-SAT algorithm past roughly 540 million variables, and the Lean theorem proves a weaker bound that beats plain 2^n only when n has about 2,400 digits. The paper itself notes that P versus NP is untouched, and OpenAI says it seeks no academic credit and will fund a conference on the result.
Why it matters: Useful for readers tracking AI-generated mathematics because it separates the asymptotic claim from practical impact and details exactly what the Lean formalization does and does not establish.