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 . 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 nonincremental HSEARCH and LSEARCH.