# The Exponential Time Refutation

> Source: <https://blog.computationalcomplexity.org/2026/10/the-exponential-time-refutation.html>
> Published: 2026-10-28 19:15:04+00:00

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.