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.
There is literally not one aspect of the universe that is provably finite. Not in any direction, not at any scale, not in any way you can think to look at it.
Maybe I misunderstand you, but I don’t think I agree with that.
E.g. the observable universe is finite. Its observable age is finite. The number of known elementary particle types is finite. The number of particles within the observable universe is finite (according to the current understanding). Etc.
There are many examples.
Do we disagree on this, or am I perhaps misunderstanding your position here?
Observable universe is just the part of the universe from where light had time to hit the Earth already. It is growing pretty much at the speed of light, not because of physical changes to the space-time, but because the light from farther away finally arrived. So while it's definitely finite, I wouldn't say it disproves the claim that nothing about the universe is known to be finite.
Key word is provably. We can assume the universe is finite because we don't have evidence against it, but no one knows if it's possible to prove or reject that for good.
I have the exact opposite experience. There nothing I can think of that is infinite in nature. Not only is it impossible to prove infinity empirically ("in the universe"; the only thing that actually matters) but there are exactly zero actual things with an infinite nature of any kind that I can think of. It's a useful imaginary construct that makes fancy math work, that's all.
And yet the vast majority of physicists treat infinity in the equations as a sign of them being incomplete, and dismiss the possibility of the universe being infinite in any way
I would like to point out that there is also no proof of God not existing either
I 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.
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.
Yep, ranting against galactic polynomial algorithms reminds me of the people who oppose the use of infinity. Like, yes, it's not physically realistic construction, but it makes things simple enough that we can do analytic solutions to problems and simplify terribly complicated things.
Polynomials are closed under multiplication, so you can do a poly algorithms poly number of times and still have a poly algorithm. That's very convenient.
It's just irrelevant for big-O complexity what happens for instances below a constant threshold, so the algorithm uses the simplest approach and moves on. If you have an exponential-time algorithm that's faster than brute force for small instances, you can use that and get a faster overall runtime at the same big-O complexity. If you can lower the switchover threshold, ditto. It's a bit weird to dismiss the subexponential algorithm just because it's leaving an obvious optimization on the table... it can only get faster from here.
This 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
I think the common expression is to miss the forest (big picture) for the trees (details). But maybe you're playing on words and saying we shouldn't let the big picture (big O notation/analysis) obscure our attention to the details (an algorithm's actual efficiency and performance).
Did you ever pause to consider that theoretical computer science might not be done for the sake of midwit code monkeys whose deepest contact with complexity theory was when they learned to reverse a linked list in O(n) for their SWE interview?
I'm not sure that retreating to the ivory tower is a winning rhetorical strategy.
Not sure why the hostility anyways. If appreciating TCS results really is a higher brow activity, then GP's indignation at computational models shouldn't upset you, quite the opposite. It's definitionally the normal experience.
And while I do find the blogpost in the OP trite, that is mostly because it's from someone who should absolutely be more intimate with the subject than such "midwitted code monkeys" (aka. normal people) you refer to, yet pretends to feel duped by OAI's results. Quite the different case, and I think is much more worthy of ridicule as a result. They're the high brow who should be appreciating, understanding, yet fail to.
I 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).
I don't think it matters? It's completely standard for "galactic" algorithms and not relevant to big-O runtime.
The complaint that these algorithms aren't "realistic" is ostensibly valid, but you could just as well aim that cannon at 95%+ of math research too. Complexity theory is interesting and fun. Isn't that enough?
I hate to use absolutely but it absolutely does matter from an education perspective. To put things in perspective to a layperson explain to them this particular galactic theorem requires full search below some titanic |x|. That should prompt some excellent lay questions that a serious computer scientist ought to reckon with.
It is not to say the approach has been wrong (as the author strongly believes in his reframing) but that this clarity does matter for purposes of, ahem, mathematical understanding.
Author 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.
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.
E.g. the observable universe is finite. Its observable age is finite. The number of known elementary particle types is finite. The number of particles within the observable universe is finite (according to the current understanding). Etc.
There are many examples.
Do we disagree on this, or am I perhaps misunderstanding your position here?
Or provaly infinite.
I would like to point out that there is also no proof of God not existing either
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.
Polynomials are closed under multiplication, so you can do a poly algorithms poly number of times and still have a poly algorithm. That's very convenient.
Surely it cannot be necessary for the complexity result?!
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
I think the common expression is to miss the forest (big picture) for the trees (details). But maybe you're playing on words and saying we shouldn't let the big picture (big O notation/analysis) obscure our attention to the details (an algorithm's actual efficiency and performance).
Not sure why the hostility anyways. If appreciating TCS results really is a higher brow activity, then GP's indignation at computational models shouldn't upset you, quite the opposite. It's definitionally the normal experience.
And while I do find the blogpost in the OP trite, that is mostly because it's from someone who should absolutely be more intimate with the subject than such "midwitted code monkeys" (aka. normal people) you refer to, yet pretends to feel duped by OAI's results. Quite the different case, and I think is much more worthy of ridicule as a result. They're the high brow who should be appreciating, understanding, yet fail to.
The complaint that these algorithms aren't "realistic" is ostensibly valid, but you could just as well aim that cannon at 95%+ of math research too. Complexity theory is interesting and fun. Isn't that enough?
It is not to say the approach has been wrong (as the author strongly believes in his reframing) but that this clarity does matter for purposes of, ahem, mathematical understanding.
Very gonzo, but maybe I prefer to learn about these things with a little less circlejerk.