The Exponential Time Refutation

In this week's big news (though it's only Wednesday), OpenAI announced a proof that the exponential-time hypothesis is false, with a Lean proof. Later Anthropic released their own paper. Ryan O'Donnell and Shiva Kintali posted follow-up proofs, smartly focusing on simplicity rather than getting the best bounds. OpenAI will partner 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, 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. Ryan also mentions Bernardo Subercaseaux's observation 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.
• If SETH is true then the 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 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.