OpenAI's 'Subexponential' SAT Algorithm Is Exhaustive Search for the Next 10^10^10^10^10^10^10 Years
Efficient algorithms, the Exponential Time Hypothesis, and losing the plot
OpenAI claimed a subexponential-time algorithm for satisfiability, but the procedure only kicks in after a threshold of 10^10,000,000,000,000,000,000,000,000 variables—a number dwarfing the universe's 10^80 atoms. Until then, it runs exhaustive search, the very method Jack Edmonds called 'bad' in 1965. The author argues this reveals how poorly we've defined algorithmic efficiency, and predicts P=NP will turn out true only in some galactic sense.
The claimed subexponential algorithm for satisfiability is definitive evidence that our definition of efficient was even worse than we thought it was 50 years ago. The answer tells us nothing about efficiency or goodness.
- emil-lp
About ETH: Many people say now that ETH was simply stated in a too strong manner, and that the correct exponential time hypothesis is SH, the Satisfiability Hypothesis.
It is almost the same as ETH, but allows for non-polynomial improvements in the exponent (which is what was proved by Clause/ChatGpt).
Recommended reading:
- inkysigma
I’ve seen quite a few critiques of the practicality of time complexity analysis but I’ve never seen an article describe what we should replace it with. Time complexity analysis, as given, has given some structure to the infinite zoo of problems even if imperfect and composes relatively nicely and is relatively simple. It’s also tractable, has mathematical structure, and is often practical as a heuristic (the kinds of algorithms people typically encounter or come up are typically reasonable under this kind of analysis). In order to be a proper substitute, something would have to satisfy all these qualities. Without such a substitute, we are back to analyzing problems and their complexity without any sort of framework which seems even worse than just remembering that sometimes the big O is not practical.
The only candidate that would be more practical that I know of is cache complexity for cache oblivious algorithms but that’s much more complicated.
- simiones
This author seems to really mis-understand complexity theory and in what ways it matters. The choice of exponential = bad and polynomial = good may have been quasi-arbitrary initially, but it since found a much more solid footing.
Exponential complexity is what you automatically get when your algorithm is "generate a possible solution, verify if it's correct, repeat if it's not". Polynomial complexity is what you get when the problem itself has some kind of structure that you can exploit to either directly construct a solution, or to generate a very small set (relative to the problem size) of possible solutions that have to be checked by hand.
Now, it is true that for all practical problem-solving purposes, "P = NP but only with algorithms that require n^10^80 or more time (with this as a proven lower bound for even the typical case, no hope of improving)" would be exactly equivalent to "P != NP". However, it would still be a mathematically extremely interesting result, as it would tell you that any problem where it is easy to verify if a solution is correct carries some hidden structure that makes it "easy" to generate the solutions. And it could still open the door to finding new sub-classes of actually easy instances of these problems that are not known today, even if the worse case remains just as intractable.
Now, note the refutation of ETH with the new algorithm found by AI is not really that impressive, it doesn't seem to have that deep of an implication. Sub-exponenti […]
- throwaway713
That's a very long-winded way of saying "I'm an ultrafinitist"...
- QuesnayJr
This is another rant about the author's bugaboo.
It would be great to prove that there is or isn't a non-galactic polynomial-time algorithm for NP-complete problems. But we can't even solve the easier problem of proving there is or isn't a galactic polynomial-time algorithm, so what hope is there for the harder problem?
If you could prove that any polynomial-time algorithm for NP problems had to be galactic, you would be the most celebrated computer scientist since Turing. It's just no one has any idea how to do that.