** Next:** Previous Work on Incremental
** Up:** Survey of Universal Search
** Previous:** Near-Bias-Optimal Nonincremental Universal Search

##

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 .
In fact, it can be made smaller than , where
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 do not even make sense within
this universe, both LSEARCH and HSEARCH may be viewed
as academic exercises demonstrating that the notation
can sometimes be practically irrelevant despite its
wide use in theoretical computer science.

** Next:** Previous Work on Incremental
** Up:** Survey of Universal Search
** Previous:** Near-Bias-Optimal Nonincremental Universal Search
Juergen Schmidhuber
2004-04-15

Back to OOPS main page