Asymptotically Fastest Nonincremental Problem Solver

Recently [20] developed a more complex asymptotically optimal search algorithm for all well-defined problems. Hutter Search or HSEARCH cleverly allocates part of the total search time to searching the space of proofs for provably correct candidate programs with provable upper runtime bounds; at any given time it focuses resources on those programs with the currently best proven time bounds. Unexpectedly, HSEARCH manages to reduce the constant slowdown factor to a value smaller than $5$. In fact, it can be made smaller than $1 + \epsilon$, where $\epsilon$ is an arbitrary positive constant (M. Hutter, personal communication, 2002).

Unfortunately, however, HSEARCH is not yet the final word in computer science, since the search in proof space introduces an unknown additive problem class-specific constant slowdown, which again may be huge. While additive constants generally are preferrable to multiplicative ones, both types may make universal search methods practically infeasible--in the real world constants do matter. For example, the last to cross the finish line in the Olympic 100 m dash may be only a constant factor slower than the winner, but this will not comfort him. And since constants beyond $2^{500}$ do not even make sense within this universe, both LSEARCH and HSEARCH may be viewed as academic exercises demonstrating that the $O()$ notation can sometimes be practically irrelevant despite its wide use in theoretical computer science.

Back to OOPS main page