cross-posted from: https://lemmy.world/post/53647234
OpenAI (and allegedly anthropic?) had models prove that the ETH is false. The proof is short, relatively easy to read, and the construction is not esoteric: I believe this is very likely correct.
The Exponential Time Hypothesis (ETH) is the conjecture that it takes exponential time to solve 3-SAT. 3-SAT (short for satisfiability) asks how long it takes a computer to find a solution to a boolean equation of the form (A or not B or C) and (not A or D or E) and (F or not C or D) … where there are $n$ boolean variables and $m$ clauses. It was believed that this should take, essentially, $(4/3)^n$ time for the fastest algorithm (roughly equivalent to brute forcing all possible boolean values for the variables).
But it is possible to do much better. They give a divide-and-conquor algorithm based on polynomial interpolation that runs in roughly $2^{n/log(n)}$ time (which grows slower than $b^n$ for any $b>1$). This implementation isn’t useful for SAT instances smaller than the universe, so internet security is fine. But often these algorithms get improved.
This is shocking; it was pretty widely believed that ETH was the reason that P!=NP. It has fallen; will any other barrier survive?
(I acknowledge that folks do not like AI solving open questions in math, there are many reasons this is bad for the community. This problem is not like most problems; this is closer to curing cancer than painting a picture. ETH has consequences, and if this approach has a shred of improvement over existing SAT solvers (which it does, or a human would have published this earlier), it will save energy, lives, and resources for humanity for awhile to come.)
You must log in or register to comment.
Isn’t 2^{n/logn} still faster-growing than any polynomial?
Yes. Perhaps the wording is unclear? This doesn’t show P=NP. It shows that P and NP are closer than we expected; that a barrier which many many professionals thought was rock solid is not. There were good reasons to believe ETH; there are not many good reasons (at least right now) to believe $2^{n/logn}$ is optimal.
This post is false. The result is unverified. Many of these so-called results have turned out to be fake. Nobody should ever trust Sam Altman and fellow grifters. They’re just trying to keep the hype train rolling until it explodes off the tracks.
On October 26, 2026, OpenAI claimed to have disproved ETH.[10][11][12][13][14] The company is asking academics to check the work before anyone treats it as settled.[12] As of October 26, 2026, the claim has not been peer reviewed. OpenAI stated future review of the proof would be done in collaboration with complexity researchers Russell Impagliazzo, Ramamohan Paturi, and Ryan Williams.[10][3] Anthropic then also announced an internal Claude model on October 16th had also disproved ETH and published the details on GitHub. - https://en.wikipedia.org/wiki/Exponential_time_hypothesis
It’s also worth noting that this result doesn’t change the unknown status of P/NP.
this is closer to curing cancer than painting a picture.
No, this is definitely not curing cancer.
I’m making an evaluation as an area expert. I think this is very likely to hold.
