Abstract

In this paper, we study the lattice of r.e. subspaces of a recursively presented vector space V ∞ with regard to the various complexity-theoretic speed-up properties such as speedable, effectively speedable, levelable, and effectively levelable introduced by Blum and Marques. In particular, we study the interplay between an r.e. basis A for a subspace V of V ∞ and V with regard to these properties. We show for example that if A or V is speedable , then V is levelable . We also show that if A is an r.e. subset of a recursive basis for V ∞ , then A is levelable iff V is speedable while it is not the case that A is levelable iff V is speedable. We also provide several contrasts between the lattice of r.e. subspaces and the lattice of r.e. sets with respect to these speed-up properties. For example, every maximal set is levelable but we show that there exist supermaximal spaces which are nonspeedable in all possible r.e. degrees as well as supermaximal spaces which are levelable in all r.e. degrees which contain levelable sets