UC Berkeley

From the original definition of a set whose jump is as simple as possible (A' =_T 0'), to more recent definitions involving randomness, notions of lowness appear throughout recursion theory. In that spirit, a non-recursive set A will be said to be low for speed if for any recursive set R and any computation of R from A, there is an oracle-free computation of R that is no more than polynomial-time slower than the A-computation.

We will construct such an r.e. set and discuss some properties of these sets. We will show that promptly simple r.e. sets cannot be low for speed, and also that there are non-prompt sets that are not low for speed. We conclude by showing that generic sets are low for speed if and only if P = NP.