The fastest and shortest algorithm for all well-defined problems (2002)

Re:The fastest and shortest algorithm for all well-defined p... by sova on Wednesday May 26, 2021 @01:07AM (#27286609)

>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 ﬁnite 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?

[ Parent | on HN ]

Re:The fastest and shortest algorithm for all well-defined p... by qsort on Wednesday May 26, 2021 @03:13AM (#27287349)

It'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.

[ Parent | on HN ]

Re:The fastest and shortest algorithm for all well-defined p... by rwallace on Wednesday May 26, 2021 @01:48AM (#27286838)

It'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.

[ Parent | on HN ]

Re:The fastest and shortest algorithm for all well-defined p... by MrYellowP on Wednesday May 26, 2021 @09:43PM (#27298410)

I don't understand why it's supposedly counter-intuitive that the fastest code is also amongst the shortest. Makes perfect sense to me?

[ Parent | on HN ]