Comment by ThePhysicist
2 hours ago
I find the paper about beating O(n log n) for integer multiplication also quite fishy, not sure but it seems like too good to be true, I feel like there must be a subtle flaw in that. Maybe that's just me hating these small numbers in the paper, but it seems wrong, unnatural even! I would be similarly skeptical about a physics paper that claims to be able to exceed the speed of light by a tiny fraction. There's no reason n log n is the natural limit here but I see a few good intuitions so having something else that can't be represented in an elegant form seem very "unmathematical" to me.
I'm not familiar with the paper you mention. But it's also worth pointing out that afaik the n log n algorithm itself isn't particularly practical. It's one of these "galactic algorithms" that is asymptotically more optimal, but is so complicated that it's only a real improvement for comically large n. And that's without even considering the mental overhead of implementing and maintaining the thing.
Of course, that's not to say the research is necessarily useless. It's still theoretically interesting to find "better" algorithms if only to shed some light on lower bounds, and so on. And who knows, maybe the line of research could lead to more practical algorithms later on.
I'm no expert, but using multitape TM for this feels to me like a wrong level of abstraction. The whole thing has a lot of smell.
I didn’t read the paper but can’t this just be additionally with doing the actual muls? Or was it a nonconstructive proof?
Surely it's a galactic algorithm that you can't physically run? You wouldn't get a constant as small as 2^{-182} without some other numbers elsewhere being incredibly large.
From the "Introduction" section of that paper: "The constants and thresholds in the construction are extremely large".
(And verifying if the algorithm multiplies correctly or not is the less-interesting part of this, anyway. Gets you no closer to verifying the complexity result).
Isn't it possible that all of the integers that have been or will ever be encountered, anywhere, any time, in human history, number less than 2^182? In which case you could argue that integer multiplication is O(1) via LUT :)
someone else picked up that bit of math and has run with it and has refined it downwards multiple times. believe it is now in the range of 2^-18 or so
1 reply →