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.
I'm very confused on improvement size. I swear I've seen log^3/2 discussed somewhere and also remember seeing log^1, not sqrt in the openai's paper. Is my memory playing tricks on me or there's just a lot of simpler versions around or what?
ReplyDeleteAlso, should we now define a "LNP" complexity class, for problems reducable to SAT with linear increase in size, in case we never get cosnt^n^o(1) algorithms? ...Or I guess "eNP" for easy-NP that can be reduced with size increase covered by current best algo
Nitpicking, but it is enough to get a 2^n^eps time alg for 3-SAT for any eps to get subexp for all of NP.
ReplyDeleteThank you for the post, and thank you to Ryan and Shiva for their simplified papers.
ReplyDeleteIt is great to see how our research community is positively engaging with these.
Two questions I have after skimming through Ryan and Shiva's articles:
1. It is not clear to me if all these techniques used were already known and AI just combined them or the AI came up with some new technique or idea that can be used to attack other problems as well.
2. Looking at Shiva's article, it looks to me this is a result that a strong PhD student surprised by Ryan or Shiva (or other young strong complexity theorists) could have come up with, it they were familiar with the tools and put their focus on this for a few years. Am I wrong to think so?
@Lance, frankly I am a bit concerned about how OpenAI picked these three researchers. Selection bias or active volunteering on their end? Would it not make much more sense to pick you for instance, and Bill Gasarch .... I'm disappointed how OpenAI has handled a few things and I would personally be avoiding them, and their LLM knowingly how terrible they have been at abusing data and enabling transparency.
ReplyDeleteLast bit, I would have politely declined such an invite. The way they have been holding xxx and flexing muscle ... has had enough of an impact so far.
They picked Russell, Mohan and Ryan because they are well-respected researchers and closely connected to ETH and SETH. I'm perfectly happy that it's them and not me.
DeleteOpenAI did claim 2^{0.49n} for Subset Sum. https://github.com/openai/math/blob/main/preprints/Subset-Sum-in-Time-2-power-0-49n-October-4-2026/subset-sum.pdf
ReplyDeleteWhich was impressive, but not 2^{o(n)}.
DeleteHilariously, OpenAI’s galactic algorithm for resolving the Exponential Time Hypothesis runs an exponential-time subroutine if the number of variables is less than 10^10,000,000,000,000,000,000,000,000.
ReplyDeleteHilariously, it seems that a lot of folks never grasped Knuth's TAOCP, especially the intro chapter on asymptotic notation.
DeleteIf I am not mistaken, we get a similar "sublinear exp" time complexity for fixed-linear-size CircuitSAT wrt the number of variables, and thus puts an end to upper bounds c^g for general CircuitSAT wrt the number of gates (whatever c one proves, for small circuits the Anthropic-OpenAI algorithm will be better; for large circuits bruteforcing 2^n assignments will be better). However,it does not give "sublinear exp" immediately in this setting unless we examine the exact asymptotics.
ReplyDelete