3 ms·
>An interesting and counter-intuitive consequence of Theorem 1, derived in Section 7, is that the fastest program that computes a certain function is also among
by sova 5y ago
>An interesting and counter-intuitive consequence of Theorem 1, derived in Section 7, is that the fastest program that computes a certain function is also among the shortest
programs that provably computes this function. Looking for larger programs saves at most a finite number of computation steps, but cannot improve the time order.
Pretty cool paper, it's from 2002 that's amazing. I'm having trouble locating the factor of five explanation. Why 5? Is it just the safest lowest bound they could guarantee without too much prodding?
- rwallace 5y agoIt's a purely arbitrary number, arising from the choice of an 80/20 division of CPU cycles between exploring and exploiting. You have to choose some number; pretty much any choice would work more or less equally well here, though there is a sense in which 2 would be the simplest/most natural choice.
- qsort 5y agoIt's the lowest they could find. From section 5: The factor of 5 may be reduced to 4 + ε by assigning a larger fraction of time to algorithm C. The constants cp and dp will then be proportional to 1/ε. We were not able to further reduce this factor.
- MrYellowP 5y agoI don't understand why it's supposedly counter-intuitive that the fastest code is also amongst the shortest. Makes perfect sense to me?