The Exponential Time Hypothesis Is False [pdf]

While this has no immediate bearing on P-vs-NP, it is interesting to note:

- Early CS researchers like Donald Knuth entered CS in the days when regularly someone would come up with a surprising faster algorithm for some problem, and their intuitions were that most problems had faster algorithms than you'd expect.

- Later generations of CS researchers, as all the easy algorithms were discovered, and post Karp's definition of NP-completeness (and the Garey & Johnson book, say), began to specialize in proving hardness, and complexity theory with a “zoo” of complexity classes became more about separation and lower bounds, e.g. I've seen algorithms like Arora's PTAS for Euclidean TSP being described as a “failed attempt to prove a lower bound”. So an entire generation of researchers' intuition was mostly in the direction of an elegant universe with neat separation results (even if we couldn't get them).

- So e.g. surveys of computer scientists showed most of them believing that P≠NP, and someone like Knuth has always seemed a bit of an outlier for saying that maybe P=NP: his argument was simply that there are so many possible polynomial-time algorithms that we haven't explored, and maybe one of them with a large exponent could solve NP-complete problems. (In response to arguments that many researchers have failed to find any such algorithms, he would say that many researchers have failed to prove that P≠NP.) E.g. in 2017 when Scott Aaronson wrote his survey (https://www.scottaaronson.com/papers/pnp.pdf = https://www.scottaaronson.com/papers/pnp-kindle.pdf) he wrote:

> Admittedly, it can be hard to tell whether declarations that P = NP are meant seriously, or are merely attempts to be contrarian. However, we can surely agree with Knuth and Lipton that we’re far from understanding the limits of efficient computation, and that there are further surprises in store.

- What we've seen in this month is surprising unexpected algorithms, like o(n log n) algorithms for FFT and integer multiplication, and now this sub–exponential-time algorithm for 3-SAT. (Yes the ETH has had less support than P≠NP but I still gather it's unexpected.)

So (though I don't expect intuitions on P≠NP to change, and probably that's still the right intuition… but I'm just an interested amateur), maybe there will be a bit of a swing of the pendulum back to the idea that maybe clever algorithms exist that we just haven't thought of.

This is an amazing and unexpected result. To be clear though, it does not imply that NP is subexponential: "Note that runtime bounds of the form 2^o(n) do not transfer under general polynomial-time reductions (2^n^o(1) would be needed for this), so our result does not imply that general NP problems admit subexponential time algorithms."

Edit: To explain more, it is guaranteed that you can reduce any NP problem to 3SAT in polynomial time with a polynomial factor in input size. You still have to solve it.

If 3SAT were solvable in polynomial time, then polynomial(polynomial(x)) = polynomial(x) and you're implied to have an overall polynomial time solution.

But what we have here is that 3SAT is solveable in subexponential time. subexponential(polynomial(x)) is not guaranteed to be sub-exponential.

Further edit: The subexponential solution does carry over to any (?) problems that have can be reduced to 3SAT in a linear number of variables. They list: Counting independent sets, Counting proper q-colorings, Counting perfect matchings.

It appears that Anthropic has released a proof as well (same bounds), but with a different approach? https://drive.google.com/drive/u/0/folders/1uaWnPqWkXy1sjfsD...

Wow. Complexity class separations are really really rare.

Can an expert in sat solving comment if there's any immediate applications of the method from the paper? Or is SAT solving in general pretty far away from worst-case times, and this is a theoretical algorithm which would be hard to apply in practice.

It's surprising that Exponential Time Hypothesis would be false. Quoting a paper from 2022[1]:

> We prove that the time complexity of self-attention is necessarily quadratic in the input length, unless the Strong Exponential Time Hypothesis (SETH) is false[...]

If OpenAI's proof is correct, does that mean self-attention can be implemented in sub-quadratic time? I.e. we could eventually have all the most advanced LLMs running on cheap hardware? To put it more playfully, is ETH being false actually bearish for Nvidia?

[1]: https://arxiv.org/abs/2209.04881

Anthropic also claims a disproof of the ETH, posted here:

https://news.ycombinator.com/item?id=50255159

NP looking a little more P than usual

I wonder how long it'll pay for frontier labs to use compute this way?

I'm reminded of the Apollo program that was cool for a while, but eventually the public lost interest.

Maybe it becomes cheaper? Maybe other labs want to prove their worth will pick up the slack when another loses interest?

It would be interesting to see if this new counting method has any implications to counting 2SAT or parity-counting of 2SAT. Since problem posed in XORSAT and 2SAT clauses is NP-complete, this could have implications about P vs NP.

I am long out of this game, but the complexity class they show still has an n in the exponent, even if divided by log(n).

I have no intuition whatsoever on how that algorithm scales. Can anyone enlighten me?

Can someone ELI5 ETH for those of us who slept through theoretical CS classes? Asking for a friend...

This seems huge, like not quite p=np but in the same league. Am I missing something ?

Double-checking, is this more like the recent DFT improvement where even the word-RAM model of computation doesn't justify the fraction of a log factor they eliminated because of an assumption of arbitrary-precision arithmetic, or has ETH actually fallen with the Lean proof being formulated appropriately? Do we know yet?

No practical implications, we dont use 10^87 variables (a point where the proposed new method surpasses the already existing sat solvers), however a good theoritical point.

I still think P != NP, I would assume 2^{n/log(n)} is an elegant optimal boundary.

This construction splits the space into 'small' models with a quadratic lookup cost and 'large' with sub-exponential cost. The small one is by enumerating all SAT problems with their answers, then looking up the answer. The large one is something in polynomials I don't understand. An answer from openai about where the cutoff is was:

    the constructed lookup machine has vastly more states than the estimated total number of physically distinguishable configurations of the observable universe.

So on balance, if this is considered proof that the exponential time hypothesis is false, and openai model reading of the lean was vaguely on point, then I reject the axioms of this system. Not a proof, even if there is lean. I'm OK with being downvoted for that position.

If I can "count the satisfying assignments of a k-CNF in subexponential time and polynomial space", could I just count the the solutions for assignments of 0 and 1 to x_1, then proceed with whichever is greater (or nonzero), counting the solutions for x_2=0, and so on.

Doesn't that lead me to an existence proof (i.e., a solution) to a k-SAT problem in N*(subexponential_time and polynomial_space)?

And with constant folding, N is reduced by 1 on each iteration.

What obvious thing am I missing here?

What about OpenAI allowed ETH to be determined to be false that couldn't be done by humans? Was there something in particular that OpenAI's AI did that help bridge the gap to a solution?

  Higgledy-piggledy,
  Exp. Time Hypothesis:
  Runtime complexity
  Soars to the sky.

  Subexponentially,
  Tensor contractions have
  Tallied solutions for
  OpenAI.

We are living in such a weird, amazing, and miraculous time. It’s completely surreal.

Perhaps this will be the push we need to finally, seriously consider the possibility that our formalisms of “efficient” and “efficiently verifiable” algorithms correspond to nothing resembling reality, and P \in NP is actually ill-posed.

This has been marginally debated since the mid 90s, when Impagliazzo published the “5 worlds” survey. Occasionally it is brought up in talks about average case analysis. There is occasionally a workshop about it. But it has never really got the attention it deserved. How many more of these results do we need to take it seriously? (Assuming we do indeed certify it.)

I remember the olden days when LLMs couldn't count.

Any implications on what could be achieved with this information, for a non academic?

> Given this news, I’ll up my personal probability of P=NP from 3% to 5%.

— Scott Aaronson

I'm not the kind of programmer that even understands P=NP, so I'll either be way off base, or be blessed with an outsider perspective.

Considering that no human will be able to sift through these in no less than a team-decade, to verify that there's no mistake, yet still that will be massively less compute than the one necessary to produce the 'solution', isn't the empirical finding contrary to the theoretical finding being suggested? Namely that in practice we are generating these 'proofs' in a massive amount of compute time, but it will take tiny amounts of time to verify them.

Is it very useful to talk about computing in purely mathematical terms and not in empirical terms? There's very obvious truths that we are seeing here, and it seems like those that go through some sort of rigorous mathematical training kind of fail to see it. Similar to how 70% of physicians or something believe in the Many Worlds Interpretation or that time isn't real, a sort of algebraic psychosis where one is removed from a human reality that we have access to in order to attempt getting close to an 'objective reality' that is far removed from the human experience.

To some extent we are computing entities, so I don't even think that we can conceive of computing as decoupled from ourselves[1]. I know the observer effect is very often mis-cited by laymen, but I'll be damned if some computer scientists like Godel don't sound like they were up to something similar to this.

Also, here's another outsider perspective. This is obviously slop, I'm not sure how but it's obviously nerd-sniping the CS majors that understand this, because it's obviously very hard to find the flaw, but it gives epicycles energy. It's also sufficiently complex that under a bayesian analysis it is more likely that the AI has reached the limit of its processing power until it becomes confused enough to believe it has reached something significant, kind of like how I'm doing now.

[1] xkcd://1163

[flagged]

Is this really as interpetable math is fundamentally. Like wtf is this accessibility? who is this for? Do top mathematicians read this like a chapter book? Absolutely ridiculous they have all this compute and creative resources and cant make something more intuitive to help people understand it more natively

wtf......

for context (ai convo):

You're right, and I should correct my earlier phrasing. The paper does *not* merely assert existence — it gives a *specific deterministic algorithm* with a concrete, proven running time:

> A deterministic algorithm that exactly counts the satisfying assignments of a canonically encoded $k$-CNF formula on $n$ variables in time $(n+m)^{O_k(1)} \cdot 2^{O_k(n \log\log n / \sqrt{\log n})}$, using polynomial space.

The Lean formalization proves this bound. So it's a fully specified algorithm, not just "there exists one." My earlier "theoretical existence statement" framing was wrong.

*What that changes (and doesn't) for the practicality question:*

- It's a real algorithm in the sense that if you implemented it, it would terminate and give the correct answer. The proof guarantees the bound. - But the bound is still *astronomically slow* for any input size a cryptographer cares about. At $n = 1{,}000$ variables the exponent is already $\sim 1{,}000 \cdot 5 / 5 \approx 1{,}000$, i.e. $2^{1000}$ — far beyond any feasible computation. - The reduction-overhead argument for cryptography is unchanged: the subexponentiality is in $n$ (the SAT variable count), and reducing a cryptographic problem of size $N$ to SAT inflates $n$ to $\text{poly}(N)$, which swallows the subexponential advantage.

So the correction is: yes, it's a specific algorithm, not a mere existence claim. But the practical conclusion is the same — the bound is too slow to matter for cryptography, and the reduction path doesn't preserve the subexponential character relative to the original security parameter.