ON THE LATTICES OF NP-SUBSPACES OF A POLYNOMIAL-TIME VECTOR-SPACE OVER A FINITE-FIELD

In this paper, we study the lower semilattice of NP-subspaces of both the standard polynomial time representation and the tally polynomial t ime representation of a countably infinite dimensional vector space V- infinity over a finite field F. We show that for both the standard and tally representation of V-infinity there exists polynomial time subsp aces U and W such that U + V is not recursive. We also study the NP an alogues of simple and maximal subspaces. We show that the existence of P-simple and NP-maximal subspaces is oracle dependent in both the tal ly and standard representations of V-infinity. This contrasts with the case of sets, where the existence of NP-simple sets is oracle depende nt but NP-maximal sets do not exist. We also extend many results of Ne rode and Remmel (1990) concerning the relationship of P bases and NP-s ubspaces in the tally representation of V-infinity to the standard rep resentation of V-infinity.