Optimal Approximations and Polynomially Levelable Sets

A set A not in P is polynomially levelable if any algorithm for A has speedup to a polynomial infinitely often in A: precisely, if given any algorithm M for A and polynomial p, it is possible to find another algorithm $M'$ for A and polynomial $p'$, such that $M'$ runs in time $p'(|x|)$ on infinitely many inputs x in A, on which the running time of M exceeds $p(|x|)$. Intuitively, this condition states that among polynomial time computable approximations to A there is no optimal one, or one giving correct answers on a maximally large subset of A. It appears that most naturally occurring intractable sets are polynomially levelable. We prove this for sets not in P that are either “paddable,” “self-reducible,” or complete for a deterministic time class. We also discuss levelability preserving reductions, and give a simple reducibility characterization of nonlevelable sets.