3 ms·
This is what I choose to believe. Even if it is not true I will still believe it because it is so satisfying.
by zests 6y ago
This is what I choose to believe. Even if it is not true I will still believe it because it is so satisfying.
- jessriedel 6y agoYea. I've always wondered whether it was motivated purely by intuition about elegance, or whether there is another computational task that has been shown to have this feature. (The finite-length proof that an infinite tower of algorithms exist without them actually being specifiable in finite length would I guess require some Gödelian jiu jitsu?)
- woopwoop 6y agoHmm, I guess I don't get it. I feel like if you have such a sequence of algorithms A_i, you can "string them together" to get a single algorithm A which has the property that it has complexity O(n^{1 + epsilon}) for any epsilon > 0. Specifically, suppose we know that A_i requires time at most C_i + D_i n^{1 + 1/i}. Then there exists N_i such that, for any n >= N, C_i + D_i n^{1 + 1/i} >= C_{i+1} + n^{1 + 1/(i+1)}, and so can't we specify A by saying "if the input has size n where N_i <= n < N_{i+1}, perform A_i"?
- zests 6y agoThe problem is that each algorithm likely has a constant factor much larger than the previous. This does not matter for the runtime complexity of any individual algorithm but when you string them together the time complexity explodes.
- woopwoop 6y agoI'm pretty confident the construction above does not depend on any bound on the growth rate of C_i (or D_i).
- jessriedel 6y agoAn algorithm has finite length, but an infinite sequence of algorithms need not. For algorithm A to actually carry out "if the input has size n where N_i <= n < N_{i+1}, perform A_i", it needs to be able to generate the code for each of the infinite number of A_i's.
- woopwoop 6y agoI see, thanks. Yeah that kind of thing is definitely above my pay grade.
- kripke 6y agoThe choice of A_i now depends on n. The complexity of your construction is O(n^{2 + 1/argmax_i { N_i <= n}), not O(n^2).
- woopwoop 6y agoOh I wasn't claiming it's O(n), just O(n^{1+epsilon}) for any epsilon > 0. Indeed, the function inside your O is dominated by n^{2 + epsilon} for any epsilon > 0.