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.)