Three fundamental results of Levin involve algorithms or reductions
whose running time is exponential in the length of certain programs. We study the
question of whether such dependency can be made polynomial.

(1) Levin's ``optimal search algorithm'' performs at most a constant factor more slowly
than any other fixed ... more >>>