On low for speed oracles
Laurent Bienvenu Rod Downey
cs.CC math.LO 03D15, 03D25, 03D32, 03D30, 03D80 F.1.3; F.4.1











 
 

On Low for Speed Oracles
    Laurent Bienvenu 

    LIRMM
CNRS & Université de Montpellier, France

     Rod Downey

 School of Mathematics and Statistics

  Victoria University of Wellington, New Zealand

    22 November 2017
====================================================================================================================================================================================





Relativizing computations of Turing machines to an oracle is a central concept in the theory of computation, both in complexity theory and in computability theory(!). Inspired by lowness notions from computability theory, Allender introduced the concept of “low for speed” oracles. An oracle A is low for speed if relativizing to A has essentially no effect on computational complexity, meaning that if a decidable language can be decided in time f(n) with access to oracle A, then it can be decided in time poly(f(n)) without any oracle. The existence of non-computable such A's was later proven by Bayer and Slaman, who even constructed a computably enumerable one, and exhibited a number of properties of these oracles as well as interesting connections with computability theory. In this paper, we pursue this line of research, answering the questions left by Bayer and Slaman and give further evidence that the structure of  the class of low for speed oracles is a very rich one. 
 






§ INTRODUCTION





The subject of this paper is oracle computation, more specifically 
the effect of oracles on the speed of computation. 
There are many notable results 
about oracles in classical complexity, beginning with the 
Baker-Gill-Solovay result <cit.> which asserts that there are oracles A such that ^A=^A, but that there are also oracles B such that ^B ≠^B (thus demonstrating that methods that relativize will not suffice to solve basic questions like  vs ).
An underlying question is whether oracle results can say things about complexity questions in the unrelativized world.
Eric Allender and his co-authors 
<cit.> showed that 
oracle access to the sets of random strings 
could give insight into 
basic complexity questions. 
For example, in <cit.>, Allender et. al.
showed that 
∩_U ^R_K_U∩⊆
where R_K_U denotes the strings whose prefix-free Kolmogorov complexity
(relative to universal machine U) is at least their length, and 
 denotes the collection of computable sets.
Later the “∩” was removed by 
Cai et. al. <cit.>.
Thus we conclude that reductions to very complex sets like the 
random strings somehow gives insight into 
very simple things like computable sets.


Inspired by lowness notions in computability theory, Allender asked whether 
there were non-trivial sets which were “low for speed” in that, 
as oracles, they did not accelerate 
running times 
of computations by more than a polynomial amount.
Of course, as stated this makes little sense since 
using any X as oracle, we can decide membership in X in linear time, while without oracle X may not even be computable at all!
Thus, what we are really interested in is the set of oracles which do not speed-up the computation of computable sets by more than a polynomial amount. More precisely, an oracle X is low for speed if for any computable language L, if some Turing machine M with access to oracle X decides L in time f, then there is a Turing machine M' without oracle and polynomial p such that M' decides L in time p ∘ f. (Here computation time of oracle computation is counted in the usual complexity-theoretic fashion: we have a “query tape” on which we can write strings, and once a string x is written on this tape, we get to ask the oracle whether x belongs to it in time O(1)). 

There are trivial examples of such sets, namely oracles that belong to , because any query to such an oracle can be replaced by a polynomial-time computation. Allender's precise question was therefore: 



Is there an oracle X ∉ which is low for speed?



Such an X, if it exists, has to be non-computable, for the same reason as above (if X is computable and low for speed, then X is decidable in linear time using oracle X, thus – by lowness – decidable in polynomial time without oracle, i.e., X ∈). 
 
A partial answer was given by Lance Fortnow (unpublished), who observed the following.

 If X is a hypersimple and computably enumerable oracle, then X is low for polynomial time, in that if L ∈^X, then L ∈.



Allender's question was finally solved by Bayer and Slaman, who showed the following. 

 
There are non-computable, computably enumerable, sets X which are low for speed.  
 

Once their existence is established, it is natural to wonder what kind of sets might be low for speed. A precise characterization seems currently out of reach, but it is interesting to see how lowness for speed interacts with other computability-theoretic properties. One needs however to keep in mind that lowness for speed is not closed under Turing equivalence: as we saw above that in the 0 degree (computable sets) some members are low for speed and others that are not (on the other hand it is easy to see that if A is polynomial-time reducible to B and B is low for speed, then A is also low for speed). 

In his PhD thesis, Bayer showed that if X is computably enumerable and of promptly simple Turing degree, then X is not low for speed, but also proved that this did not characterize the computable enumerable oracles that are low for speed. Bayer also studied the size of the set of low for speed oracles, where `size' is understood in terms of Baire category. Surprisingly, whether the set of low for speed oracles is meager or co-meager depends on the answer of the famous =? question. 

In this paper, we continue Bayer and Slaman's investigation on the set of low for speed oracles. In the next section, we give an easier proof of the existence of non-computable low for speed oracles which does not require the full Bayer-Slaman machinery (but the oracle we construct is not computably enumerable). In Section <ref>, we focus on the computably enumerable low for speed oracles, and prove that – quite surprisingly – they cannot be low in the computability-theoretic sense, but can however be low_2. Finally, we pursue Bayer and Slaman's idea to study how large the set of low for speed oracles is, in terms of measure and category. In particular, we solve a question they left open by showing that the set of low for speed oracles has measure 0 and obtain some interesting connections with algorithmic randomness. Finally, though lowness for speed is not closed under Turing equivalence

it is nonetheless natural to ask which Turing degrees contain a low for speed member, which is what Section <ref> is about. 

Throughout this paper, we will denote by  the set of finite strings. In our setting, an oracle is a language, i.e., a subset of ; however, as is typical in computability theory, it is more convenient in some of the results we present below to view oracles as infinite binary sequences (whose set we denote by ), by first identifying finite strings with integers (the (n+1)-th string in the length-lexicographic order being identified with n) making the oracle a subset of  (which is what we mean when we talk about a `set' without further precision) and then identifying the oracle with its characteristic sequence (the (n+1)-th bit is 1 if n belongs to the oracle, 0 otherwise. When building oracles X with certain computability-theoretic properties, viewed as infinite binary sequences, we will often need to refer to prefixes of X, which are themselves binary strings. To avoid confusion between members and prefixes of oracles, we will use latin letters x, y, z, … to denote members of oracles, and greek letters σ, τ, … for prefixes of oracles. Two strings σ and τ are incompatible if for some i < min(|σ|,|τ|), σ(i) ≠τ(i). We denote this by σ  τ. The join X ⊕ Y of two infinite binary sequences X, Y is the sequence X(0)Y(0)X(1)Y(1) …. Finally X  n is the prefix of X of length n. 

Our paper requires some knowledge of computability theory and algorithmic randomness. One can consult the book <cit.> for the results and concepts we allude to below. Our notation is mostly standard.  We denote Cantor's pairing function by ⟨ .,. ⟩. We also fix an effective list (Φ_e) of all oracle Turing functionals (or machines: Φ_e^A is the Turing machine of index e with oracle A, which for a fixed A is a partial function from  to {0,1}). For a given functional Φ_e and oracle A, time(Φ_e^A,x) denotes the running time of Φ_e on input x with oracle A (counting time according to the model of computation described above) and time(Φ_e^A) is the function x ↦ time(Φ_e^A,x). We let (R_i) be an effective enumeration of all partial computable functions from  to {0,1}. We denote the set of low for speed oracles by , and the subset of  consisting of its non-computable elements by . 







§ EXISTENCE OF NON-COMPUTABLE LOW FOR SPEED SETS



In this section we will present a simple proof of the existence of a non-computable low for speed oracle. Define the set  of strings by = {0^2^n| n ∈} 
and let  be the set of `sparse' sets of strings which only contain strings from , that is, = {X ∈|  X ⊆}. 

By extension, we say that a string σ is in  if it is a prefix of some element of . 
The interest of the set  is that there are only O(n) strings in  of length n. Thus, given a Turing machine Φ, it is possible to simulate in time poly(t) the behaviour of Φ^X during t steps of computation on all X ∈ (an idea which is already present in the Bayer-Slaman argument presented in the next section). 


There exists a non-computable X which is low for speed. 




We want X to satisfy all requirements ℛ_(e,i), where e,i range over integers, defined as follows


ℛ_(e,i): either R_i is partial, or Φ_e^X ≠ R_i, or  Φ_e^X = R_i but the computation of R_i via Φ^X_e can be simulated by a functional Ψ running in time polynomial in time(Φ^X_e).


We build our oracle X by finite extension. Let σ_0 be the empty string. At stage s+1=e,i, do the following. 


  (a) If there is an n and a τ∈ extending σ_s such that Φ_e^τ(n) and R_i(n) both converge and have different values, then let σ_s+1 be the first (say in length-lexicographic order) such string τ. 

  (b) If there is no such string τ, then take σ_s+1 = σ_s 0


Finally let X be the unique infinite sequence extending all σ_s. We claim that X is as wanted. Let us first prove that X must be incomputable. Suppose X=R_i for a total R_i. Let e be an index such that Φ_e is the identity functional. By construction, when choosing the prefix τ of X at stage s+1=e,i, we must be in case (a), and thus τ is precisely chosen to ensure X ≠ R_i, a contradiction. Let us now prove that X is low for speed. Fix a pair (e,i) let s+1=e,i, and let us see how σ_s+1 was constructed. If we were in case (a) at that stage, we have ensured Φ_e^σ_s+1   R_i and thus Φ_e^X   R_i, thereby satisfying ℛ_(e,i). If we were in case (b), there are three subcases:


  * Either R_i is partial, then the requirement ℛ_(e,i) is satisfied

  * Or there is an n such that Φ_e^τ(n) ↑ for any extension τ of σ_s, in which case Φ_e^X(n) ↑ and thus Φ_e^X ≠ R_i should R_i be total. 

  * Or, if we are in neither of the two above cases, for every n there is an extension τ of σ_s such that Φ_e^τ(n) ↓, and for any such τ, we have Φ_e^τ(n) = R_i(n). In this case, we can build a functional Ψ which computes R_i as follows. On input n, at stage t, it computes Φ_e^τ(n) during t steps of computation for all τ∈ of length t extending σ_s. If a τ is found such that  Φ_e^τ(n) ↓, then we set Ψ(n)=Φ_e^τ(n). As we already mentioned, there are only O(t) strings of length t in  and it is obvious that they can be listed in polynomial time. Hence, simulating all computations Φ_e^τ(n) during t steps can be done in time p(t) for some polynomial t. This shows that for any Y ∈ extending σ_s, if Φ_e^Y(n) returns (the value of R_i(n)) in time t, this is found out by the procedure Ψ at stage t, which corresponds to ∑_s ≤ t p(s) +O(1) steps of computation for Ψ, which is also polynomial in t. This being true for any Y ∈ extending σ_s, we have in particular that time(Ψ) = poly(time(Φ_e^X)). 



One should note that the case disjunction in this proof is a Σ_1/Π_1 dichotomy, and therefore one can carry out the construction below ', therefore establishing the existence of a '-computable set that is low for speed. This is weaker than the Bayer-Slaman result presented in the next section, which asserts the existence of a c.e. such set. However, this proof is both simpler and, as we will see in the remainder of the paper, has further useful corollaries. 







§ COMPUTABLY ENUMERABLE LOW FOR SPEED SETS


We now restrict ourselves to the computably enumerable (c.e.) sets, and study which of these can be low for speed. For the sake of completeness, we present the main ideas of the proof of Bayer and Slaman <cit.> that there are indeed c.e. sets in . 



There exist c.e. non-computable sets that are low for speed.



The proof uses a tree-of-strategies argument. We need to satisfy

    _e: A W_e,

and

    Ł_e,i:  Φ^A_e =R_iΨ
    R_i time(Φ_e^A).

The _e-strategy is a standard Friedberg-Muchnik strategy on a  tree. 
A node ρ devoted to this requirement picks a fresh follower 
x, waits for x∈ W_e[s] and if this happens puts x into A. 

The basic strategy for Ł_e,i is the following. First, throughout the whole construction of A, we will promise that if we add an element x to A at stage t, then we must immediately also add all y ∈ [x,t] (this is often referred to as a  dump construction). This way, at any stage s, there will only be at most s strings α of length s that can potentially be a prefix of (the final) A. And thus – just like in the previous section – at stage s, it is possible to emulate all computations Φ_e^α(x)[s] for all such α's and x ≤ s in time poly(s). 

When the strategy is eligible to act at stage s, for every x ≤ s on which Ψ is not defined yet, it computes all Φ_e^α(x)[s] for all potential prefixes α of A, and should one of them converge, defines Ψ(x) to be the value of Φ_e^α(x) for the α that has the fastest convergence. If no Φ_e^α(x)[s] converges, Ψ(x) remains undefined until the strategy is eligible to act again. 

Now, if at some later stage we find a value x such that R_i(x) ↓ and Ψ(x) ≠ R_i(x), then we find the α such that Ψ(x) = Φ_e^α and add elements into A so that α becomes a prefix of A. This ensures Φ_e^A ≠ R_i and terminates the strategy. All strategies of lower priorities are then injured and must be reset. If we never find such an x, this means that either Φ_e^A is partial, or R_i is, or Ψ = Φ_e^A = R_i and by construction the running time of Ψ is polynomial in the running time of Φ_e^A.[Actually, there is a subtlety here: one must ensure that the strategy for Ł_e,i is eligible to act often enough, i.e., allowed to act for the n-th time before stage q(n) for some polynomial q, but this can easily be ensured.]

This is enough to ensure the success of the strategy in isolation. The difficulty comes from the interaction with lower-priority strategies which might want to add elements into A. The final key to the Bayer-Slaman proof is the following. Suppose that at some stage s a strategy of lower priority wants to add an interval [y,s] of elements into A. The problem is that 
the computations on this configuration might be slow. Perhaps for some 
x of length ≤ s we have not as yet seen 
Φ_e^A_s∪ [y,s](x)↓. Even more importantly, we don't even know 
that the value of this will agree with the value Ψ(x) we have already defined.

The idea is the following. R_i has to confirm the computations, that is, we wait until R_i(x) converges on all x where Ψ has already been defined. When (and if) this happens, we must have Ψ(x)=R_i(x) for all such x otherwise we would be in the above case where we can ensure Φ_e^A ≠ R_i and satisfy the requirement. If this never happens, our requirement will be satisfied because R_i would be partial. And if it does happen, then we can safely add [y,s] to A because if this causes Φ_e^A(x) to change, it will yield Φ_e^A(x) ≠ R_i(x) which satisfies the requirement. But there is one last problem: while waiting for this confirmation, the construction of Ψ cannot wait as we need it to be as fast as Φ_e^A. The crucial trick is, from the point of view of our strategy, to carry on as if [y,s] had already been enumerated into A. Indeed, if the confirmation ever happens, the elements of [y,s] will be truly enumerated into A which Ψ will have correctly assumed ahead of time, and if the confirmation never happens, Ψ might be wrong (i.e., Ψ≠Φ_e^A)  but this will not matter because in this case R_i will be either partial or different from Φ_e^A. 
Of course, when the confirmation never occurs the strategy of lower priority never gets to enumerate into A the elements it wants. This is where we make use of a standard tree construction where strategies of lower priorities guess the outcome of strategies of higher priority. We refer the reader to <cit.> for details. 





Within the c.e. sets, would one expect a set to be low for speed to 
have low or high information content?  In particular, one would expect that a low for speed c.e. set would 
be one with little computational power, in the same way that 
sets low for 1-randomness are all (super-)low (see Nies <cit.>). The next theorem is therefore quite surprising. 

  If A is c.e. and of low Turing degree
(i.e. A'≡_T ∅'), then A is 
not low for speed.



Assume that A is not computable, is c.e., and is low. Let (Φ_e,p_e) be an enumeration of pairs of one functional and one polynomial with coefficients in . We will build a Turing functional Ψ and a computable set R such that Ψ^A=R. This is our global requirement and we make the following global commitment: if a value R(n) gets defined at some stage, Ψ^X(n) is immediately defined to be equal to R(n) for all X's on which Ψ^X(n) is still undefined. We want to satisfy, for each e:
 
    (ℛ_e): Φ_e does not compute R in time p_e(time(Ψ^A))

thus proving that A is not low for speed. The strategy for a single requirement (ℛ_e) is the following. Throughout the construction, we build a `verifier',  i.e., a partial computable S such that S(e,.) is the attempt by the (ℛ_e)-strategy to guess A. We also define an auxiliary functional Θ common to all strategies whose index we know in advance, and use the lowness of A to obtain a computable 0-1 valued function h(.,.) such that lim_t h(e,t) exists for all e, and equals 1 when Θ^A(e) ↓, 0 otherwise. (Informally, Θ^X(e) ↓ means that a prefix of X is believed to be a prefix of A at some stage of the strategy for (ℛ_e), and this will cause the strategy to enter Case 3 as described below.)

At the initial stage s_1, S is empty and we pick a first fresh witness w_1 larger than any integer mentioned so far in the construction and define Ψ^A_s_1 1(w_1)=0. Let t_1 be the time this computation takes. Now, check whether Φ_e(w_1) returns in p_e(t_1) steps. We distinguish three cases:


Case 1: Φ_e(w_1) returns 1 in ≤ p_e(t_1) steps. In this case, we set R(w_1)=0 and R(n)=0 for all n ≤ w_1 on which R is still undefined, and commit to having Ψ^A(w_1)=0 even after potential future A-changes. This way we ensure Φ_e ≠ R = Ψ^A, thus immediately satisfying (ℛ_e), and we stop the strategy for this requirement. 





Case 2: Φ_e(w_1) returns 0 in ≤ p_e(t_1) steps. In this case, we do not define R(w_1) just yet. Instead, we set S(e,1)=A_s_1 1. We then create a second witness w_2 at stage s_2 and proceed as above for this new witness (with A_s_2 2 in place of A_s_1 1). And so on: for further occurrences of this case, the procedure will extend S and create a witness w_3 at stage s_3 looking at prefixes of length l=3, etc (and if Case 2 then causes a reset, we stay at the same level l when resetting). Meanwhile, we continue to monitor A. Again, there are two subcases for a given l: 


  (a) At some point we discover that A_s_l i is not in fact an initial segment of A, we are then free to set R(w_l)=1 (which will guarantee Ψ^A(w_l)=1 =R(w_l) ≠Φ_e(w_l) since we only committed to Ψ^σ(w_l)=0 for σ's that are not prefix of A), and this way we have satisfied (ℛ_e). We then stop the strategy. 

  (b) A_s_l l is a true initial segment of A, in which case nothing further will happen regarding witness w_l. What is gained is that S(e,l) will be defined to be A_s_l l = A  l, thus progress was made towards computing A.




Case 3: Φ_e(w_1) is still undefined after p_e(t_1) steps. In this case, we set Θ^A_s_1 1(e) ↓ (which should be interpreted as signalling that we have entered Case 3). Observe that is A_s_1 1 is a true prefix of A, this implies Θ^A(e) ↓ and therefore we would have lim h(e,t) = 1. We distinguish two subcases



  (a) The current value h(e,s) is 0. Then we wait for a stage t>s such that either h(e,t)=1 or  A_t 1 ≠ A_s  1 (one of the two must happen as we explained above). If the former happens first we move to subcase (b) below. If the latter happens first, we restart the procedure resetting s_1 to the current stage t and keeping the same w_1. 

  (b) The current value h(e,s) is 1. We then set R(w_1)=0, set R(n)=0 for all n ≤ w_1 on which R is still undefined and terminate the strategy for now. However, if at a later time t>s, we see that h(e,t)=0 and A_t  1 ≠ A_s_1 1, then we resurrect the strategy and start over at the level i where we left off. 



We claim that this strategy satisfies the requirement (ℛ_e). If Case 1 happens for any witness w_l, the requirement is satisfied. Case 3a can only happen finitely many times at a given level since as A_s_l l can only change finitely many times. Case 3b can only happen finitely many times across all levels as each passage through this case causes a flip of h(e,.), and we know h(e,.) converges. Case 2b can also happen only finitely often, because each time we go through this case and do not get to diagonalize, S(e,.) computes a longer initial segment of A, but A is incomputable so S(e,l) would eventually have to be wrong.

Thus we either eventually end up in Case 1 (and immediately succeed) or Case 2a (and immediately succeed) or a terminal Case 3b, i.e., the strategy enters Case 3b and stays there forever. It remains to check this last scenario. Suppose the terminal Case 3b happens for some A_s_l l which is not a prefix of A, this means that Ψ^A(w_l) has not been defined yet and thus, should nothing else happen, we would have lim_t h(e,t)=0 and would see a change in A  l, thus leaving this occurrence of Case 3b, a contradiction. So A_s_l l is indeed a prefix of A and by construction Ψ^A(w_l) returns 0=R(i) in a number of steps t while Φ_e(w_l) does not return in less than p_e(t) steps, thus the requirement is satisfied. It is now straightforward to satisfy all requirements by ordering them in order of priority, noticing that each strategy only makes finitely many changes to R before achieving its goal and R is total as every time R(w) becomes defined, so do the R(n) for n ≤ w that were previously undefined. 






It is important to note that the above result fails to hold outside of the c.e. setting. 


There exists a low, non-computable set X which is low for speed. 



See Section <ref>.




We next ask whether Theorem <ref> is tight in terms of the 
lowness/highness hierarchy. Recall that 
A is low_2 if 
A”≡_T ∅”.

 
There is a low_2 c.e. set that is low for speed.



This time we must build A to satisfy additionally to _e and Ł_e:

    _e: (Φ_e^A  is total) → (Θ_e  is total).

where (Θ_e) is a sequence of functionals we build.





The basic idea is that at stages where the length 
of convergence 
ℓ(e,s)=max{x| (∀ y ≤ x) Φ_e^A(y)[s]↓} 
increases we would like to preserve this computation and set Θ_e(x) ↓. We think of this having subrequirements 
_e,x devoted to preserving Φ_e^A(x)[s].

There is an apparent conflict between our requirements. Suppose we have three requirements _i, Ł_j, _k, in decreasing order of priority, and _k believes that Ł_j will have infinitary outcome. At some point, _k wants to enumerate some element x into A. As we saw in the previous construction, Ł_j will start behaving as if x had already entered, while _k waits for confirmation before actually doing so. However, if at some point in the process _i imposes a restraint containing x, this will prevent x from entering A and thus destroys Ł_j's plan to add x after confirmation, and the functional Ψ built by Ł_j might just be wrong. One can check that any other interaction between requirements does not cause any conflict. 

The solution to the problematic case is to look closer at the tree of strategies. If the strategies for Ł_j and _k are working under the assumption that _i has finitary outcome (waits forever to preserve Φ_e^A  x for some x), there is no problem: if it is indeed the case they will not be bothered by any restraint _i might impose, and if they are wrong they will not be on the true path anyways. So the problematic case only happens if they are working under the assumption that _i has infinitary outcome (arbitrarily long restraints). The idea is, under the assumption that the requirement _i has infinitary outcome, to break it down to subrequirements _i,x devoted to preserve Φ_i^A  x) and place them below on the tree, interleaved with other strategies. So now we are down to the case where Ł_j and _k are working below an _i,x, under the assumption that _i has infinitary outcome. But then there is no problem at all: because of the infinitary assumption, the strategies for  Ł_j and _k can both wait for _i,x to place its restraint, and then only allow bigger elements to enter A, thus respecting this restraint. 

There is no other difficulty to take care of when putting the strategies on a tree, except a small detail: when an -strategy operate below an Ł-strategy assuming infinitary outcome, when the Ł strategy behaves as if some x has already entered A, then so should the -strategy. The rest is routine. 




We can also combine the  the same ideas (dump construction together with awaiting for certification) with the standard proof that there exists an incomplete c.e. set A of high Turing degree (i.e., A' ≡_T ∅”) to get the following. 

 
There is a high c.e. set A which is low for speed.


Note that we do not say in the theorem that A is Turing incomplete, because this in fact follows from lowness for speed, as we will see in Proposition <ref>. 




§ HOW BIG IS ?


Bayer and Slaman showed that whether  is meager or not... depends on the answer to  vs  question! More precisely, if =, then  is co-meager (more precisely, every 2-generic is low for speed), while if ≠, then  is meager (more precisely, every recursively generic is not low for speed). They left as an open question whether  has measure (Lebesgue) 0 or 1 (by Kolmogorov's 0/1-law, it has to be one or the other). One might expect that, just like the meagerness of  depends on the   vs  question, its measure depends on complexity-theoretic assumptions, such as the ` vs ' question. This is not the case: we show that  is – unconditionally – a nullset. 


The set  has measure 0. Indeed, no Schnorr random is low for speed. 




We first build a computable set R with the following properties: (1) the set R contains at most one string of any given length and (2) for all e, if Φ_e computes R, then time(Φ_e,x) > 2^|x| for almost all x. To do so, we declare at the beginning of the construction all indices e `active', and for every n in order, do the following. We compute Φ_e(x) during 2^|x| of computation for all x of length n and all currently active e ≤ n. If for some pair (e,x) we see that Φ_e(x) converges, we take the smallest such pair in the lexicographic order (smallest e first, then smallest x), we diagonalize against Φ_e by setting R(x) = 1-Φ_e(x) (thus ensuring Φ_e ≠ R), as well as R(y) =0 for all y ≠ x of length n, and then declares e inactive from now on. If no such pair (e,x) exists, set R(y)=0 for all y of length n. This finishes the construction of R. It is clear that R is computable (it is even in ) and that it contains at most one string of each length. To verify property (2), suppose Φ_e computes R, and observe that for any x such that time(Φ_e,x) ≤ 2^|x|, the only way Φ_e can escape being diagonlalized against by R is when some Φ_i with i<e is diagonlized against on strings of length n, but this can only happen e times. Thus if Φ_e does indeed compute R, it must do so in time 2^|x| for almost all x. 

Now we need to see how to speed up computations with a Schnorr random oracle. Consider the following procedure Ψ. Given oracle Z and input x, Ψ^Z(x) first splits Z (viewed as a binary sequence) as Z=ζ_1 ζ_2 … with |ζ_i|=i and Ψ^Z(x) returns 0 if x=ζ_|x| (thus the resulting computation is polynomial in |x|), and Ψ^Z(x)=R(x) otherwise, using a fixed procedure to compute R. So there is a polynomial p such that for any Z, time(Ψ^Z,x) ≤ p(|x|) for infinitely many x's. Furthermore, we can only have Ψ^Z(x) ≠ R(x) if x=ζ_|x| and ζ_|x| happens to be the only string of its length in R. This has probability at most 2^-|x| (`at most' because R can also have no string of length |x| at all) if Z is chosen at random. This means that, by setting C_n = {Z | (∃ x)   |x| = n ∧ Ψ^Z(x) ≠ R(x)}, we have λ(C_n) ≤ 2^-n. 

The C_n's are uniformly computable clopen subsets of  because Ψ is a tt-functional. Thus, a Schnorr random A can only belong to finitely many C_n's (see for example <cit.>), meaning that Ψ^A(x)=R(x) for almost all x. Thus there is a finite variation Ψ̂ of Ψ such that Ψ̂^A=R, and  Ψ̂^A(x) is computed in polynomial time for infinitely many x while time(Φ_i,x)>2^|x| for any Φ_i computing R and almost all x. This shows that A is not low for speed. 


On the other hand, we will see in the next section that  is large in the set-theoretic sense, namely that it has the size of the continuum. 

Finally, there is one last notion of size for subsets of  that is dear to computability theorists, namely, a set is `large' if it contains a Turing upper cone and is `small' if it disjoint from a Turing upper cone. Martin's Turing determinacy theorem tells us that any Borel set which is closed under Turing equivalence must be either large or small on this account. The set  is indeed Borel (this is easy to see from the definition), but it is not closed under Turing equivalence, so Martin's theorem does not apply. In the next section, we will use a classical result from complexity theory to show that  is in fact disjoint from a Turing upper cone (Theorem <ref>). 





§ LOWNESS FOR SPEED AND TURING DEGREES
 





While lowness for speed is not closed under Turing equivalence, the following question is nonetheless interesting: 


Which sets are Turing equivalent to some low for speed X? Which sets compute some non-computable low for speed X?


(Of course the analog question for non-low for speed is trivial: every A ∈ is equivalent to A ⊕ L for some 𝖤𝖷𝖯𝖳𝖨𝖬𝖤-complete language L, and clearly A ⊕ L is not low for speed as L is not; thus every degree contains a member that is not low for speed). 



We denote by  and  the set of Turing degrees that contain a low for speed set and a non-computable low for speed set, respectively. One of the main results of Bayer <cit.> is that not all degrees are in . Indeed, there exists a c.e. degree 𝐚∉. The main question left open by Bayer regarding  is whether it is downward closed under ≤_T or closed under join. We give a negative answer to both questions. To show that it is not downward closed, we need the following extension of Theorem <ref> to degrees. 


For any low c.e. degree 𝐚>0, we have 𝐚∉. 




We now suppose that A only is of c.e. degree (as opposed to being c.e.) and is low. Let (A_s) be a Δ^0_2 approximation of A, and let μ be its modulus of convergence, i.e., μ(n) is the smallest s such that all {A_t | t ≥ s} have the same prefix of length n (which must thus be the prefix of A of length n). Observe that μ is a lower semi-computable function, and let μ_s be its approximation at stage n (setting μ_0(n)=0 for all n). 

The fact that A has c.e. degree is equivalent to the fact that μ is A-computable (see <cit.>), so let M be a functional such that M^A(n)=μ(n) for all n. Consider the set { X ∈| M^X(n)=k }. This is an effectively open set, uniformly in (n,k) and thus can be represented by a c.e. set of strings that are pairwise incomparable for the prefix relation (by this, we mean that an X is in M^-1(n,k) if and only if one of these strings is a prefix of X), and this representation is effective and uniform in (n,k). We call P(n,k) the set of strings which both belong to this set and are a prefix of some approximation A_s of A. Observe the following easy facts:


  (i) P(n,k) is c.e. uniformly in (n,k)

  (ii) P(n,k) is finite for all (n,k). 

  (iii) If k ≠ k', then any two strings σ∈ P(n,k) and τ∈ P(n,k') are pairwise incomparable for the prefix order.

  (iv) A has a prefix in P(n,μ(n)) for all n (and thus no prefix in other P(n,k) for k ≠μ(n) by the previous fact). 

Facts (i), (iii) and (iv) follow directly from the definition. Fact (ii) holds because the sequence (A_s) pointwise converges. 

We now adapt the construction of R and Ψ as in the proof of Theorem <ref>. The strategy to win against a pair (Φ_e,p_e) still works by levels, with a verifier S which this time attempts to compute μ (it will eventually fail because if μ were computable, so would be A), and again an auxiliary functional Θ, with h(.,.) a computable approximation of Θ^A, by lowness of A. Also, as before, as soon as R(n) becomes defined, Ψ^X(n) is immediately set to be equal to R(n) for any X on which Ψ^X(n) was still undefined. Our strategy starts with l=1 and S undefined everywhere, and does the following. First, it looks at the current value k=μ_s(l) and starts enumerating P(l,k). When a new string σ enters P(l,k), we pick a fresh witness w=w(l,σ) for this σ, set Ψ^σ(w)=0, look at the number t of steps this computation takes, and compute Φ_e(w) during p_e(t) steps of computation. Once again, there are three cases which will require different actions for this σ:


Case 1: Φ_e(w) returns 1 in ≤ p_e(t) steps. In this case, we set R(w)=0 and R(n)=0 for all n below the current stage on which R is still undefined, and stop the strategy forever.  


Case 2: Φ_e(w) returns 0 in ≤ p_e(t) steps. We set S(e,l)=k. We then start again the procedure with l+1 and 
 


  (a) If at some point we discover that μ(l)>k, we are then free to set R(w)=1, R(n)=0 for all n below the current stage on which R is still undefined, and stop the strategy forever. 

  (b) μ_s(l)=μ(l), in which case S(e,.)  has made progress towards computing μ. 



Case 3: Φ_e(w) is still undefined after p(t) steps. In this case, we set Θ^σ(e) ↓. We have the same two subcases as before:



  (a) The current value h(e,s) is 0 (here, this should be interpreted as the fact that ∅' currently does not believe that any of the strings that have been enumerated so far in P(l,k) and reached Case 3 is a true initial segment of A). Then we wait for a stage t>s such that either h(e,t)=1 or to see a new σ enter P(l,k), or to see an increase of μ so that μ(l)>k. If h(e,t)=1 happens first, we move to subcase (b) below. If a new σ enters P(l,k), we set R(w)=0 and R(n)=0 for all  and run the strategy on the new σ. Finally, if μ(l) increases above k, then we know that we have not seen any prefix of A yet at this level, so we restart the procedure at the same level with the new value of k. 

  (b) The current value h(e,s) is 1. We then set R(w)=0, set R(n)=0 for all n below the current stage on which R is still undefined and terminate the strategy for now. We resurrect the strategy at this level if we see either a new σ entering P(l,k) or an increase in μ(l). 


On top of the action for a single σ that enters P(l,k), if at any point of time we see a τ that enters P(l,k), picks a witness w_τ and lands in Case 1 or Case 2, then we immediately stop the action of the other σ's that we have seen so far in P(l,k), and for all of those, copy the action of τ on witness w_τ.  This is in fact only important in Case 2, the reason being that we do not want the action of a `bad' σ (i.e., not a true prefix of A) to interfere with the strategy on a good σ that enters Case 2, as the bad σ would otherwise (by going through Case 3 and defining R(n) for the n needed by the good σ). 

The rest of the verification is pretty much the same as before, with the additional point that we can only go through Case 3 finitely often at a given level because h can only flip finitely many times and P(l,k) is a finite set, and go through Case 2b only finitely often otherwise S(e,.) would be a computation of μ. 








 is not downward closed under ≤_T, even within c.e. degrees. 



Let 𝐚>0 be a c.e. degree in  whose existence was explained in Section <ref>. By Sacks's splitting theorem <cit.>, there is a low c.e. degree 0 < 𝐛 < 𝐚. By Theorem <ref>, 𝐛∉. 


The next theorem will show that while not every c.e. degree contains a low for speed member, every non-zero c.e. degree 𝐚 bounds a degree 𝐛∈. Recall Bayer's result that whether 2-generics are low for speed or not depends on the ` vs ' question. When it comes to the degree of generics, we have that every 1-generic is Turing-equivalent to a set that is low for speed, independently of complexity-theoretic assumptions. 


Every 1-generic degree 𝐠 belongs to . 



We get this result by refining the proof of Theorem <ref>. In that proof, we built an X low for speed by finite extension, and ensuring that X was a subset of = {0^2^n| n ∈}. For G ⊆, let _G= {0^2^n| n ∈ G}. We claim that when G is 1-generic, _G= {0^2^n| n ∈ G} is low for speed (and clearly _G ≡_T G). In the proof of Theorem <ref>, if we let 𝒰_ℯ,𝒾 be the effectively open sets of those Z such that for some n, Φ_e^S_Z(n) and R_i(n) both converge to different values, we know that G, being 1-generic, is either in 𝒰_e,i (hence satisfying the requirement ℛ_e,i as per case (a)), or in the interior of the complement of 𝒰_e,i, which precisely corresponds to case (b), hence the requirement is also satisfied in this case. 


We can derive a number of useful corollaries from this theorem. First of all, we see that  has the size of the continuum since G ↦ S_G is one-to-one, and there are continuum many 1-generic G. We also get an immediate proof of Theorem <ref> that asserts the existence of a set of low degree that is low for speed. 


Take a Δ^0_2 1-generic G; the corresponding set _G is low for speed and is low as it is both Δ^0_2 and of GL_1 (Indeed a result of Jockusch <cit.> states that every 1-generic degree G is GL_1, that is, G' ≡_T G ⊕∅'; when G ≤_T ∅', this is equivalent to G' ≡_T ∅').
 

 A similar idea allows us to show that  contains a non-trivial interval in the Turing degrees.


There is a degree 𝐚 >0 such that every 0≤𝐛≤𝐚 is in .
 


By a result of Haught <cit.>, if 𝐚 is a Δ^0_2 1-generic degree, every 𝐛>0 below 𝐚 is of 1-generic degree. Then the result follows immediately from Theorem <ref>.


Another interesting corollary is that every non-computable c.e. set bounds a non-computable low for speed set. Likewise almost every set, in the measure-theoretic sense, bounds a non-computable low for speed set. 


Every non-zero c.e. degree bounds a member , every 2-random degree bounds a member of . 



This is simply because every non-zero c.e. degree and every 2-random degree bounds a 1-generic degree <cit.>. 




We now show that  avoids a cone, namely all degrees above 0'. 




If 𝐚≥0', then 𝐚∉. 



The proof of this theorem relies on the proof of a classical computational complexity theorem, namely Blum's speed-up theorem <cit.> (see also <cit.>), which asserts that for every sufficiently fast growing computable function f, there exists a computable set R which admits no fastest algorithm in that for every i such that Φ_i=R, there is a j such that Φ_j=R and f(time(Φ_j,x)) ≤ time(Φ_i,x) for almost every x. 

Blum's theorem is proven as follows. We build R by diagonalization against all Φ_i, where for all x in order we try to find an `active' i ≤ |x| such that Φ_i(x) converges in less than f^|x|-i(|x|) steps, and if such an i is found, we set R(x) = 1 - Φ_i(x) for the smallest such i, and declare i inactive from that point on (since we have already ensured Φ_i ≠ R, we no longer need to deal with Φ_i). If no such i is found, set R(x)=0. By construction, R is computable, and any Φ_i computing it must satisfy time(Φ_i,x) ≥ f^|x|-i(|x|) for almost all |x| ≥ i (otherwise, Φ_i would be diagonalized at some point, because for any x such that time(Φ_i,x) < f^|x|-i(|x|), the only way Φ_i can escape diagonalization is when some other Φ_j with j<i is diagonalized in priority, but this situation can happen at most i times). Now, suppose Φ_e is a functional that computes R. We need to show that there is another functional which computes R much faster than Φ_e. Fix a large k and assume we are given as `advice' the finite list σ_k of indices i < k such that Φ_i eventually gets diagonalized against (and therefore i becomes inactive) in the construction of R. Now, we can compute R via the following procedure. In a first phase, simply follow the construction of R as described above, until we reach a point where all i ∈σ_k have become inactive. At this point, we know (only because we know σ_k!) that none of the {Φ_i | i  < k} are relevant for the construction of R on future x. Thus, we enter a second phase where to compute each R(x), we only need to simulate, for k ≤ j ≤ |x|, Φ_j(x) during f^|x|-j(|x|) steps of computation. By dovetailing, this can be done in poly(|x| · f^|x|-k(|x|)) (the polynomial being independent of k) which, if f is fast growing enough and k large enough compared to e, is < f (f^|x|-e(|x|)), which in turn is < f(time(Φ_e,x)) for almost all x (note that such a k can be computed uniformly given e). 

Now, suppose we are given A ≥_T ∅'. Let f(n)=2^n and R the corresponding set in Blum's theorem. Note that in the above, determining whether a given i will eventually become inactive can be done uniformly relative to ∅', and thus the list σ_k can be computed uniformly in k relative to ∅'. Thus, using A as oracle, we can consider the procedure Ψ^A which for each pair (Φ_e,p_e) of a functional and a polynomial sequentially, finds the k and σ_k  above, checks whether e ∈σ_k, in which case there is nothing to do as Φ_e ≠ R by definition, and if not, use the above 2-phase method to compute R, until a large x is found such that f(time(Ψ^A,x))<time(Φ_e,x), which for x sufficiently large guarantees p_e(time(Ψ^A,x)) < time(Φ_e,x), and we can then move on to the next index e+1. 





There are 𝐚,𝐛∈ such that 𝐚∨𝐛∉



Let G_0 be 2-generic, i.e., 1-generic relative to ∅'. Consider G_1 = G_0 Δ∅' where Δ is the symmetric difference. It is easy to check that G_1 is also 2-generic. Thus S_G_0 and S_G_1 (defined as in the proof of Theorem <ref>) are both low for speed but S_G_0⊕ S_G_1≥_T G_0 ⊕ G_1 ≥_T G_0 Δ G_1 = ∅', so by the previous theorem, deg(S_G_0⊕ S_G_1) ∉. 


After generic degrees, let us move to random degrees. We have seen in Theorem <ref> that  is a nullset, and in fact no Schnorr degree is low for speed. Interestingly, this result does not extend to Turing degrees: by a result of Nies et al. <cit.>, every high degree has a Schnorr random member and we have seen that there is a low for speed of high degree. This leaves open the possibility that almost all X are Turing-equivalent to a low for speed set. This would be similar to the category situation where – under the reasonable assumption ≠ – the set  is meager (as proven by Bayer and Slaman) but the set of A's whose degree is in  is co-meager (Theorem <ref>). This is not the case however: if we increase the algorithmic randomness level from Schnorr randomness to Martin-Löf randomness, then the distinction disappears.


 
If 𝐚 is, or simply bounds, a Martin-Löf random degree then 𝐚∉ (equivalently: if A ∈ computes a Martin-Löf random, A is not low for speed). 


Note that this shows in particular that {A | deg(A) ∈} has measure 0, and also that any A ≥_T ∅' is not low for speed, as Chaitin's Ω number is Martin-Löf random and Turing equivalent to ∅'. 

Instead of proving Proposition <ref> directly, we will prove the  following stronger theorem.


If 𝐚 is a DNC degree, then 𝐚∉ (equivalently: if A ∈ computes a DNC function, A is not low for speed). 


Proposition <ref> follows from this theorem because DNC degrees are closed upwards, and by a result of Kučera <cit.>, every Martin-Löf random degree is a DNC degree. 


The proof of this theorem relies on the proof of a classical computational complexity theorem, namely Blum's speed-up theorem <cit.> (see also <cit.>), which asserts that for every sufficiently fast growing computable function f, there exists a computable set R which admits no fastest algorithm in that for every i such that Φ_i=R, there is a j such that Φ_j=R and f(time(Φ_j,x)) ≤ time(Φ_i,x) for almost every x. 

Let us first discuss how to prove Blum's speed-up theorem. As it happens, we have already seen a proof with similar features, namely the proof of Theorem <ref> (this is no coincidence, as it is the proof Blum's speed-up theorem that inspired this other proof). We build R by diagonalization against all Φ_i, where for all x in order we try to find an active i ≤ |x| such that Φ_i(x) converges in less than f^|x|-i(|x|) steps (here the exponent is understood as composition: f^0 is the identity, and f^n+1=f ∘ f^n) and if such an i is found, we diagonalize against Φ_i by setting R(x) = 1 - Φ_i(x) for the smallest such i, and declare i inactive from that point on. If no such i is found, set R(x)=0. Obviously R is computable, and the same argument as in the proof of Theorem <ref> shows that for any Φ_i computing R, one must have time(Φ_i,x) ≥ f^|x|-i(|x|) for almost all x. Now, suppose Φ_e is a functional that computes R. We need to show that there is another functional which computes R much faster than Φ_e. Fix a large k and assume we are given as `advice' the finite list σ_k of indices i < k such that Φ_i eventually gets diagonalized against (and therefore i becomes inactive) in the construction of R. Now, we can compute R via the following procedure. In a first phase, simply follow the construction of R as described above, until we reach a point where all i ∈σ_k have become inactive. At this point, we know (only because we know σ_k!) that none of the {Φ_i | i  < k} are relevant for the construction of R on future x. Thus, we enter a second phase where to compute each R(x), we only need to simulate, for k ≤ j ≤ |x|, Φ_j(x) during f^|x|-j(|x|) steps of computation. By dovetailing, this can be done in poly(|x| · f^|x|-k(|x|)) (the polynomial being independent of k) which, if f is fast growing enough and k large enough compared to e, is < f (f^|x|-e(|x|)), which in turn is < f(time(Φ_e,x)) for almost all x (note that such a k can be computed uniformly given e), and this finishes the proof of Blum's speed-up theorem. 

Looking more closely, the core of the argument is that for a given x and a given i, if we somehow knew that Φ_i is not diagonalized againstexactly at that point x, then we can save the computation of Φ_i(x)[f^|x|-i(|x|)] in the computation of R(x). We already see why DNC-ness naturally comes into play. Let θ : → be the partial computable function such that θ(i) is the one string x on which Φ_i is diagonalized against during the construction of R, and θ(i) ↑ if there is no such x. Having a DNC function as oracle allows us to find, for any given i, a y ≠θ(i) should θ(i) be defined, and thus one can speed up a bit the computation of R(y) for this y. In fact we can do much better: by a result of Jockusch <cit.>, having access to a DNC function allows us to uniformly avoid a finite number of values of a given partial recursive function. Here this means that with our DNC oracle, we can, uniformly in k, find a y ∉θ(i) for any i<k on which θ is defined, or equivalently, a y such that none of the Φ_i with i<k gets diagonalized at y. Applying Blum's argument, one can indeed use this information to truly speed up the computation of R(y). We are not quite done yet however: our argument shows that once we have computed y from k we can speed-up the computation of R(y), but the computation of y itself might take a long time and offset the time we save on the computation of R(y). 

To overcome this problem, we need to refine the above idea. Let .,.,. be the canonical `tripling' function: a,b,c = a,b,c and for 1 ≤ i ≤ 3, let π^i_3 be the i-th projection (π^i_3(x_1,x_2,x_3)=x_i, note that these function are polynomial-time computable). Since A has DNC degree, again using Jockusch's result, A computes, via a fixed functional Ξ, a function F such that F(k) ≠π^2_3(θ(i)) for any i<k on which θ is defined (here and in the rest of the proof we identify strings and integers). Said otherwise, for any pair (a,c) of integers, none of  the functionals {Φ_i | i<k} gets diagonalized against at y=a,F(k),c. 

Now let Ψ the functional which computes R as follows using oracle A. On input x, it first computes the projections of x, i.e., finds k,l,m such that x=k,l,m. Then, it tries to compute F(k) via Ξ and using oracle A during m steps of computation. If it fails to do so, it then computes R(x) using a fixed procedure (with no access to the oracle) and returns this value. If it does succeed to compute F(k), it then checks whether l=F(k). If not, Ψ^A(x) again returns R(x) using a fixed procedure to perform the computation, without access to the oracle. Finally, and this is the interesting case, if F(k) is computed in ≤ m steps of computation, and l=F(k), we know by definition of F that none of the  {Φ_i | i<k} gets diagonalized against at x. Thus Ψ^A can compute R(x) by only simulating, like in the proof of Blum's theorem Φ_j(x) during f^|x|-j(|x|) steps of computation for k ≤ j ≤ |x|. In that case, the total computation time is still poly(|x| · f^|x|-k(|x|)) because the m steps of computation needed to get F(k) are simply poly(|x|). For a given k, taking m sufficiently large will give enough time for the computation of F(k) by A, and make x=k,F(k),m large enough to ensure that the computation time of Ψ^A(x) is < f(time(Φ_e,x)), as long as f is sufficiently fast growing. This shows that A is not low for speed. 


As an immediate corollary, we get the result mentioned in the pervious section that  is disjoint from a cone in the Turing degrees, again because DNC degrees are closed upwards. Another interesting consequence is that the analogue of the low basis theorem for Π^0_1 class does not extend to lowness for speed: it is not true that every non-empty Π^0_1 class contains a member of low for speed degree. For example, one can take a Π^0_1 class of Martin-Löf randoms: all its elements have DNC degree by Kučera's theorem, and thus do not have low for speed degree. 



At this point, we know that the set of X's which compute a member of  is very large: it has measure 1 and is co-meager, it contains every c.e. set, etc. We might even start thinking that every non-computable X computes a member of . This is not the case however, as shown by the following theorem (which contrasts Corollary <ref>). 


There is a degree 𝐚>0 such that no 0 < 𝐛≤𝐚 is in . Indeed, 𝐚 can be chosen to be a minimal Turing degree. 


Note that another way to obtain a degree 𝐚>0 such that no 0 < 𝐛≤𝐚 is in  is by taking 𝐚 to be a hyperimmune-free degree containing a Martin-Löf random member, which ensures that hat every 0 < 𝐛≤𝐚 also computes a 1-random (see <cit.>), and apply Proposition <ref>. However, the existence of a minimal low for speed degree is interesting in its own right. 


The classical construction of a minimal degree is done by forcing over total computable function trees (here we follow the terminology of <cit.>). A function tree is a partial function T: → such that if either T(σ 0) or T(σ 1) is defined, then all of T(σ), T(σ 0) and T(σ 1) are, and T(σ 0) and T(σ 1) are strict extensions of T(σ) such that T(σ0)    T(σ1) (we say that T(σ 0) and T(σ 1) split T(σ)). We say that σ is a node of T if σ∈ rng(T). A tree S is a sub-f-tree of T, which we denote by S ≼ T when every node of S is a node of T. An infinite binary sequence Z is a path on an f-tree T if infinitely many prefixes of Z are nodes of T. The set of paths of T is denoted by [T]. An f-tree naturally extends to a functional from  to ∪ by setting T(X) = ⋃_σ≼ X T(σ)  When an f-tree T is total, this extension is an homeomorphism from  to , and if T is furthermore computable, its inverse T^-1 is also computable. Given a functional Φ_e, we say that T is e-consistent if for any two nodes σ and τ on T and any n, if Φ_e^σ(n) and Φ_e^τ(n) are both defined, then they are equal; in this case, for any path X of T, Φ_e^X is either partial or computable. We say that T is e-splitting if T is total and for any σ, Φ_e^T(σ 0) and Φ_e^T(σ 1) are incomparable; in this case, the restriction of Φ_e to [T] is total, one-to-one, and its inverse is computable.








The key lemma in the construction of a minimal degree states that for any total computable f-tree T and every e, there is a total computable sub-f-tree S of T which is either e-consistent or e-splitting. Then an X ∈ of minimal degree is obtained by taking a sufficiently generic filter G over the set of total computable f-trees ordered by ≼, and take the intersection of their sets of paths (the non-computability of X can be further ensured by remarking that for any σ, the set of computable f-trees whose nodes are all incomparable with σ is a dense set for the order ≼, thus one can choose X to avoid any fixed subset of , such as its computable elements). 

We are going to prove Theorem <ref> by showing that taking a sufficiently generic filter for the order ≼ ensures lowness for speed as well. For this, we will make use of the following lemma. 


Let T be a total computable f-tree. There exists a total computable f-subtree S ≼ T none of whose paths is low for speed. 
 


The functional T^-1: [T] → is total on its domain, which is a Π^0_1 class, and thus is a tt-reduction by effective compactness. Let f be a computable time bound for the running time of T^-1, that is, for any Y ∈ [T], whether x ∈ T^-1(Y) can be decided in time f(|x|) with access to oracle Y. Now, let L be a computable set that cannot be computed in time 2^f(n+1). Let S be the sub-f-tree of T defined by S(σ)=T(σ⊕ L) (where σ⊕ L = σ(0)L(0) …σ(k-1)L(k-1) when k=|σ|). The paths of S are exactly the sets of the form T(X ⊕ L) for some X. Each of them computes L in time f(n+1) by definition of f, which is exponentially faster than any procedure computing L without oracle by our assumption on L. 



Let T be a total computable f-tree and Φ_e a functional. As we explained earlier, the usual construction of a minimal degree shows that there is S ≼ T which is either e-consistent or e-splitting. In the case S is e-consistent, we are satisfied (this guarantees Φ_e^A to be either partial or computable). If it is e-splitting, we further refine S as follows. Since S is e-splitting, we consider the total computable f-tree S' corresponding to the image of S by Φ_e: S'(σ)=Φ_e^S(σ) (this is indeed an f-tree precisely because S is e-splitting). By the previous lemma, there is a total computable S”≼ S' none of whose paths is low for speed. Now the pullback T' = Φ_e^-1(S”) is a total computable f-subtree of T, which forces Φ_e^A to not be low for speed. 

Thus we can force for all e that Φ_e^A is partial or not low for speed, and force A to be of minimal degree and be non-computable as usual. 


We do not know whether or not all sets of minimal degree are in fact non-low for speed. 



Another way to prove Theorem <ref> is to use Kumabe ans Lewis's theorem that there exists a minimal degree of DNC degree <cit.>, and apply Theorem <ref>, but our proof is more informative, as it also shows that lowness for speed is a generic notion for forcing with total with computable f-trees. 










Acknowledgements. This paper grew from interactions between complexity theory and classical computability theory originating from the 2012 Dagstuhl Seminar “Computability, Complexity and Randomness” (Seminar 12012). Bienvenu acknowledges support of ANR-15-CE40-0016-01 RaCAF grant, Downey thanks the Marsden Fund of New Zealand, and the LIRMM (University of Montpellier) where this research was undertaken.



alpha













