OpenAI says the Exponential Time Hypothesis is false
On 26 October OpenAI published a claim that the Exponential Time Hypothesis is false. If it holds up, it's a big result in theoretical computer science.
Say you have 100 switches, each ON or OFF, and a few hundred rules like "at least one of A, B or C is ON" or "D is OFF or E is ON". Is there a setting of the switches that satisfies every rule? Checking a given setting is easy. Finding one is the hard part. With 100 switches there are 2^100 settings, about 1.27 nonillion, and trying them all is out of the question.
That's 3-SAT, with each rule limited to three switches. It's NP-complete, which is why it comes up whenever people talk about P vs NP.
The hypothesis
People have been beating brute force on 3-SAT for a long time, but only by shrinking the base of the exponent. Schöning's random-walk algorithm from 1999 runs in about (4/3)^n time. Later work on the PPSZ algorithm got that down to around 1.307^n. Each of these is a real improvement, and each is still exponential: add a few variables and the running time multiplies.
In 1999 Russell Impagliazzo and Ramamohan Paturi proposed the Exponential Time Hypothesis (ETH). It says that's the best anyone can do. There's some constant above 1 that 3-SAT can't beat, so no algorithm solves it in subexponential time as the number of variables grows. A stronger version, SETH, says the constant creeps towards 2 as the rules get wider.
Nobody proved either one, but they became standard assumptions. A lot of lower bounds in parameterised and fine-grained complexity start with "assuming ETH" or "assuming SETH". One of the better-known ones is that edit distance, the measure behind spell checkers and DNA alignment, can't be computed much faster than quadratic time unless SETH is false.
OpenAI's claim
The paper is in OpenAI's math repository on GitHub, dated 17 October and revised on 25 October, along with a Lean formalisation. The abstract says:
We give a deterministic algorithm for exactly counting the satisfying assignments of an arbitrary k-CNF formula. For every fixed k >= 2, on a formula with n variables and m clauses, our algorithm uses space polynomial in n and m and runs in time (n+m)^O_k(1) 2^(n/(log n)^(1/2+o(1))).
So it doesn't only decide whether a solution exists, it counts them. Counting is at least as hard as deciding, since a count above zero means there's a solution, so this is a stronger claim than refuting ETH needs. The repo says the result came from "an unnamed internal OpenAI model".
The paper describes the algorithm as algebraic. Its overview splits the variables into groups, fixes a small number of shared measurements so that the groups can be summed independently, and then rebuilds the exact count by polynomial interpolation. Whether the details hold is what the examination is for.
The running time
The running time is subexponential, but only just. The exponent is n divided by roughly the square root of log n. For a million variables that's still about 270,000, so the bound is around 2^270000 before the constants the paper leaves hidden. The 1.307^n bound at the same size is about 2^386000. So it's not a better SAT solver in any practical sense, and I don't think anyone will be solving real instances faster because of it. It still matters, because any subexponential algorithm breaks the hypothesis, however slow it is in practice.
Consequences if it's right
The paper says the algorithm refutes more than ETH. Because it decides both satisfiability and unsatisfiability in subexponential time, it also refutes SETH, Gap-ETH, NSETH and the counting version, #ETH. It gives subexponential algorithms for counting independent sets, graph colourings and perfect matchings. Through a known link between fast algorithms and lower bounds, it also gives a superlinear circuit lower bound for a class called E^NP.
The paper is also careful about what doesn't follow. A 2^o(n) running time doesn't survive general polynomial-time reductions, so it says outright that the result "does not imply that general NP problems admit subexponential time algorithms". Some of the lower bounds built on SETH also follow from weaker assumptions that might still hold. The bounds for longest common subsequence and regular-expression matching also follow from the Orthogonal Vectors Conjecture, which may still hold.
Limits of the claim
It doesn't settle P vs NP. A subexponential algorithm is still not a polynomial one, and hard problems don't suddenly become easy.
It also isn't established yet. Impagliazzo and Paturi are organising an open, independent examination with Ryan Williams of MIT. Williams posted that they were asked to help. At their request OpenAI made the materials public straight away, so anyone can look. The paper cites his 2016 result refuting the Merlin-Arthur version of SETH.
The Lean proof helps, but it doesn't settle things either. It checks a formal statement, and someone still has to confirm that statement says what the paper says. The repo's own notes show a gap. Lean proves a slightly weaker time bound, with (log log n)^2 in the exponent where the paper's sharpest bound has log log n. It's still subexponential. The repo also has a track record to weigh. It holds 721 manuscripts, about 42% of the top-line results are formalised, and the README says "some of the unformalized results could have issues". On 7 October OpenAI withdrew three manuscripts after a sign error broke one argument and two papers that depended on it.
What interests me is how this was found and how it's being checked. A model produced the result, and the people who proposed the hypothesis in the first place are leading the review in public. I'll be watching to see whether the proof survives.