On speedable and levelable vector spaces (Q1326776)

The paper investigates complexity theoretic properties such as speedable, effectively speedable, levelable, effectively levelable, for the r.e. subspaces of a recursive infinite-dimensional vector space \(V_ \infty\). For example, it is shown that if \(V\) is an r.e. subspace of \(V_ \infty\) with an (effectively) speedable basis, or \(V\) itself is (effectively) speedable, then \(V\) is (effectively) levelable. Also, if \(A\) is an r.e. subset of a recursive basis \(B\) of \(V_ \infty\), then \(A\) is (effectively) speedable iff the subspace generated by \(A\) is (effectively) speedable. Many other results relating the above complexity theoretic properties to structural properties like maximality are presented. The questions of whether levelable or speedable subspaces of \(V_ \infty\) have a levelable or speedable basis remain open.