The exponential time hypothesis is false cross-posted from: 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. 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.)