The authors study polynomial-time presentations of vector spaces in a feasible analogue of work by G. Metakides and the first author [Ann. Math. Logic 11, 147-171 (1977; Zbl 0389.03019)]. For instance, a classic theorem of J. C. E. Dekker [Notre Dame J. Formal Logic 12, 329-334 (1971; Zbl 0205.30802)] says that a recursive vector space with a procedure that decides independence possesses a recursive basis. The authors examine various “feasible” versions of this result, many of which are shown to be oracle-dependent. The paper is very clearly written, and the authors are careful to point out the differing interpretations of “effective” presentation. The results would seem of interest not only for their own sake, but also for their obvious connections with uniform on-line algorithms.
For the entire collection see [Zbl 0753.00018].