The Exponential Time Refutation

OpenAI announced a proof that the exponential-time hypothesis (ETH) is false, publishing a paper and a Lean formalization showing that for every fixed k, a k-CNF formula with n variables and m clauses can be solved — and its solutions counted — in time (n+m)^{O(1)}·2^{O(n log log n/√log n)}. Anthropic released its own paper on the result, and Ryan O'Donnell of Carnegie Mellon and Shiva Kintali posted follow-up proofs; OpenAI said it will partner with complexity theorists Russell Impagliazzo, Mohan Paturi and Ryan Williams to verify and study the proof. Refuting ETH also refutes the strong exponential-time hypothesis (SETH), which implies ETH, undermining hardness results that depended on them, such as Clique requiring 2^{Ω(n)} time on n-vertex graphs.

In this week's big news though it's only Wednesday , OpenAI announced https://openai.com/index/building-scientific-understanding-with-academic-communities/ a proof that the exponential-time hypothesis is false https://github.com/openai/math/blob/main/preprints/The-Exponential-Time-Hypothesis-is-False-October-25-2026/paper.pdf , with a Lean proof https://github.com/openai/math/blob/main/lean/docs/378.md . Later Anthropic released their own paper https://github.com/anthropics/formal-math/blob/16a5ce41304fcdaea4e0be7c132e1c361dc26da5/eth/paper.pdf . Ryan O'Donnell https://www.cs.cmu.edu/~odonnell/some eth false exposition.pdf and Shiva Kintali https://shivakintali.github.io/papers/ETH.pdf posted follow-up proofs, smartly focusing on simplicity rather than getting the best bounds. OpenAI will partner https://docs.google.com/document/d/1adB0IhJgLzsmbfCgoLrtoJTjnlPf74UnyjMo35P5JHo/edit?tab=t.0 with three of my favorite complexity theorists, Russell Impagliazzo, Mohan Paturi and Ryan Williams to verify and study the proof. I have not verified the proof myself, but it is safe to assume now that the exponential-time hypothesis is toast. Recall 3-SAT, the problem of determining whether a Boolean formula that is an AND of ORs of three variables or their negations has a satisfying assignment. 3-SAT is the prototypical NP-complete problem from which we derive all the others. The exponential-time hypothesis ETH , introduced by Impagliazzo and Paturi in 1999 https://doi.org/10.1109/CCC.1999.766282 , building on their work with Francis Zane, states that there is a $c 0$ such that every algorithm solving 3-SAT requires time $2^{cn}$, where $n$ is the number of variables. There's also a strong exponential-time hypothesis SETH which says that for every $\epsilon 0$ there is a $k$ such that $k$-SAT cannot be solved in time $2^{ 1-\epsilon n}$. The OpenAI paper gives an algorithm that, for every fixed $k$, determines whether a $k$-CNF formula with $n$ variables and $m$ clauses is satisfiable, and even counts the number of solutions, in time $ n+m ^{O 1 }\,2^{O n\log\log n/\sqrt{\log n} }$ their Lean proof gives a slightly weaker bound . This refutes ETH, and hence SETH, which implies ETH. If you want to understand the proof, I suggest starting with Ryan O'Donnell's paper https://www.cs.cmu.edu/~odonnell/some eth false exposition.pdf . Ryan also mentions Bernardo Subercaseaux's observation https://x.com/b subercaseaux/status/2114865520055046442 that we get a nontrivial simulation of nondeterministic time on multitape Turing machines, $$ \mathrm{NTIME} T \subseteq \mathrm{DTIME}\left 2^{O T \log\log T ^3/\sqrt{\log T} }\right . $$ Researchers studied ETH and SETH because they implied many other hardness results, for example - If ETH is true then Clique requires time $2^{\Omega n }$ on $n$-vertex graphs, or $2^{\Omega \sqrt{m} }$ on graphs with $m$ edges. - If ETH is true then finding a clique of size $k$ cannot be done in time $f k \,n^{o k }$ for any computable function $f$, so the trivial $n^{O k }$ algorithm is essentially optimal https://doi.org/10.1016/j.jcss.2006.04.007 . - If SETH is true then the orthogonal vectors problem https://en.wikipedia.org/wiki/Orthogonal vectors problem on $n$ vectors of dimension $\omega \log n $ cannot be solved in time $n^{2-\epsilon}$ for any $\epsilon 0$. Bill's new badly timed book https://www.amazon.com/Computational-Intractability-Guide-Algorithmic-Bounds-ebook/dp/B0GC1VRLDB?crid=2TA3RU9KVMCAU&dib=eyJ2IjoiMSJ9.aAhGi9rIgk4KZf76JdkUZQ5aeuHh-4a0IzqFES5ZwbwEWQ8EGK 0jbiOHPTdbu8CINIsCscRYwue7gBarinOOKjwuhsYLgkS 4942wmwbIdfrGeMO5kkN0D75Kom1IDgWcDRpicm6GOWFE2jhwXV6O95FGy-reiL3QMd2vw64ygpNHNOV Hb0alI6YtLc86QoMWWGM-lWkE jfne2hKj9T9TYvOquQB LEJo4TKWZpk.vY-kFsp4lOanGt5j7BNsUrtgKqhq-s0zdeuy6MayZQw&dib tag=se&keywords=demaine+gasarch+haj+book&qid=1793212892&sprefix=demaine+gasarch+haj+book%2Caps%2C762&sr=8-1&linkCode=ll2&tag=computation09-20&linkId=e9adc435f7a1166411594b4d595b4f7d&language=en US&gaOptInStatus=true&ref =as li ss tl with Erik Demaine and Mohammad Hajiaghayi has details. The fact that ETH and SETH fail doesn't mean their implications are false. Keep in mind that the OpenAI algorithm applies to $k$-SAT but not to NP problems in general. It gives nothing new for Subset Sum or Traveling Salesman, whose best algorithms still take roughly $2^{n/2}$ and $2^n$ time, because the reductions from those problems to 3-SAT blow up the number of variables too much. Getting subexponential algorithms for all of NP would require solving 3-SAT in time $2^{n^{o 1 }}\mathrm{,}$ which the OpenAI result doesn't get close to achieving.