Brief Introduction to Optimal Universal Search

Consider an asymptotically optimal method for tasks with quickly verifiable solutions:

Recently Hutter developed a more complex asymptotically
optimal search algorithm for *all* well-defined problems
[3].
HSEARCH (for *Hutter Search*) cleverly allocates part of the total
search time for searching the space of proofs to find provably correct
candidate programs with provable upper runtime bounds, and
at any given time
focuses resources on those programs with the currently
best proven time bounds.
Unexpectedly, HSEARCH manages to reduce
the constant slowdown factor to a value of , where is an
arbitrary positive constant.
Unfortunately, however, the search in proof space
introduces an unknown *additive* problem class-specific
constant slowdown, which again may be huge.

In the real world, constants do matter.
In this paper we will use basic concepts of optimal search
to construct an optimal **incremental** problem solver that
at any given time may exploit experience collected in previous
searches for solutions to earlier tasks,
to minimize the constants ignored by
**non**incremental HSEARCH and LSEARCH.

Back to OOPS home page