<- Back
Comments (71)
- NooneAtAll5I'm frustrated with these "galactic algorithm frustration" postsbig constants are not new. We all had a laugh when matrix mul exponent went from [2.3728]639 to [2.3728]596Even more than that - reading GMP manual and seeing all the "more efficient, but bigger constant" algorithms take over each other as the size grows causes *awe*so this "sudden" discovery that theory is different from practice has been bloody obvious for everyone. I'm more inclined to say "if you want to went frustration at Ai - do that, stop showing your ignorance"---the main benefit for these results isn't to show what's possible - it's to show what's *not impossible*---also I just saw that this is the same author that wrote "Did I read this paper? Of course not. No one at OpenAI read this paper either, so why should I?"so he expects same level of discussion he deserves himself - completely negligible
- simionesThis 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-exponential running times are not that fundamentally different from exponential ones - they basically just tell you that the problem has just enough structure to eliminate a certain class of possible solutions outright, instead of spending the time to actually verify them. If the algorithm found had been polynomial, even of a huge degree, this would have been a completely different discussion. As it is, we'll just replace the ETH with a "nearly-E"TH and nothing much changes.
- inkysigmaI’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.
- BigTTYGothGFI'm a former mathematician and this bit:> Applied mathematicians often need to build a giant scaffolding of mathematical modeling to solve a problem. This scaffolding creates new mathematical puzzles that aren’t directly connected to the original problem of interest, but that entice problem solvers. You’ll then see dozens of follow-up papers solving the puzzles but forgetting the problem we cared about in the first place.really resonated with me. The pure math tail is wagging the applied math dog.
- emil-lpAbout 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: https://arxiv.org/abs/2611.02650
- throwaway713That's a very long-winded way of saying "I'm an ultrafinitist"...
- QuesnayJrThis 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.
- stabblesThe point of these "epsilon improvements" is that it challenges people's intuition. It raises the question how much further one can improve on it.
- choegerWould be great to get at least a glimpse of an understanding about why the algorithm does the enumeration in the first place.Surely it cannot be necessary for the complexity result?!
- podocarpThis reminds me of the (perhaps unrelated meme) hello I would like (graph of zeta function) number of apples. Statements dreamt up by the utterly deranged.Indeed I have met professors who claim since something is O(1) it doesn't matter if you run it 4 times. No need to optimize. I think it's just part of the wider divide between theory and application. For instance big O also requires a register machine to make sense, which most courses don't define. Somehow addition and multiplication are O(1) in some places and O(n) or O(n^2) somewhere else. Also quite common is the fact that sets are slower than lists for lookup for small n, despite being O(1).It's just a tool and we shouldn't miss the trees for the forest. I also understand this comment has nothing to do with the ETH or the article, but just some thoughts I have after reading the first chunk on complexity
- AardwolfI guess in engineering what you care about is: how fast is it on given input size X relevant for the practical problem. Or: how much input size can we do in time bound Y.
- calfI don't think the author's criticism of "Big-O Cabal" is very nuanced, but to the second half of the essay it is funny/concerning/sobering to find that the OpenAI proof is doing brute-force search for all instances below some super-astronomic threshold. It kind of buries the lede if the proof did not mention this clearly and the author has to comb through it to find out (I asked ChatGPT the same on the pdf file, but it came up with some other threshold number).
- imtringuedWell, since no one has sided with the author, let the math coin clipping keep going without pause.
- traesPost #1,000,037 complaining about AI in math by ragging on the existence of pure math. Sigh.
- anonundefined
- perching_aixAuthor is a math professor who somehow wants you to believe that he didn't know what a computational model is until OpenAI's manuscript dump a few days ago. In this post, he now extends that pretending game to galactic algorithms.Very gonzo, but maybe I prefer to learn about these things with a little less circlejerk.