Why would you expect the opposite? Tight lower bounds have not been proven for most problems, much less algorithms produced which reach such bounds, and even in the rare cases where they have been, then the constant factors could well be substantially improved. And then there are hardware improvements like ASICs, which are no joking matter. I collected just a few possibilities (since it’s not a main area of interest for me as it seems so obvious that there are many improvements left) in http://www.gwern.net/Aria%27s%20past,%20present,%20and%20future#fn3
I’m not sure really. The conjectured limits in some cases are strong. Computational complexity is unfortunately an area where we have a vast difference between what we suspect and what we can prove. And the point about improvements in constant factors is very well taken- it is an area that’s often underappreciated.
But at the same time, these are reasons to suspect that improvements will exist. Carl’s comment was about improvement “surely” occurring which seems like a much stronger claim. Moreover, in this context, while hardware improvements are likely to happen, they aren’t relevant to the claim in question which is about software. But overall, this may be a language issue, and I may simply be interpreting “surely” as a stronger statement than it is intended.
Given the sheer economic value of improvements, is there any reason at all to expect optimization/research to just stop, short of a global disaster? (And even then, depending on the disaster...)
No, not particularly that I can think of. The only examples where people stop working on optimizing a problem is when the problem has become so easy that it simply doesn’t matter to optimize further, but such examples are rare, and even in those sorts, further optimization does occur just at a slower place.
Why would you expect the opposite? Tight lower bounds have not been proven for most problems, much less algorithms produced which reach such bounds, and even in the rare cases where they have been, then the constant factors could well be substantially improved. And then there are hardware improvements like ASICs, which are no joking matter. I collected just a few possibilities (since it’s not a main area of interest for me as it seems so obvious that there are many improvements left) in http://www.gwern.net/Aria%27s%20past,%20present,%20and%20future#fn3
I’m not sure really. The conjectured limits in some cases are strong. Computational complexity is unfortunately an area where we have a vast difference between what we suspect and what we can prove. And the point about improvements in constant factors is very well taken- it is an area that’s often underappreciated.
But at the same time, these are reasons to suspect that improvements will exist. Carl’s comment was about improvement “surely” occurring which seems like a much stronger claim. Moreover, in this context, while hardware improvements are likely to happen, they aren’t relevant to the claim in question which is about software. But overall, this may be a language issue, and I may simply be interpreting “surely” as a stronger statement than it is intended.
Given the sheer economic value of improvements, is there any reason at all to expect optimization/research to just stop, short of a global disaster? (And even then, depending on the disaster...)
No, not particularly that I can think of. The only examples where people stop working on optimizing a problem is when the problem has become so easy that it simply doesn’t matter to optimize further, but such examples are rare, and even in those sorts, further optimization does occur just at a slower place.