On the lattices of NP-subspaces of a polynomial time vector space over a finite field (Q1923577): Difference between revisions

The paper investigates the semilattice of NP vector subspaces of some natural representations of a countable, infinite-dimensional vector space \(V_\infty\) over a finite field \(F\). This is a semilattice because, as is shown in the paper, the set of subspaces as above is closed under intersection but not under sum. The paper constructs oracles realizing various requirements with respect to the existence of simple NP spaces and of maximal NP spaces. For example, it is shown that the existence of P-simple subspaces and of NP-maximal subspaces is oracle dependent in the standard representations of \(V_\infty\). The paper also establishes numerous connections between P bases and NP subspaces for the two natural (tally and standard) representations of \(V_\infty\).