Complexity Theoretic Algebra I: Vector Spaces over Finite Fields
Anil Nerode, Jeffrey B. Remmel · 1987
This is the first in a series of papers on the complexity theoretic analogue of recursion theoretic algebra. It is shown that for an infinite dimensional polynomial time vector space over a finite field with a "tally representation" for vectors questions such as whether there is a maximal NP-subspace are oracle-dependent. As in recursion theoretic algebra, the main tool is the priority method.