On the lattices of NP-subspaces of a polynomial time vector space over a finite field

Annals of Pure and Applied Logic 81 (1-3):125-170 (1996)


In this paper, we study the lower semilattice of NP-subspaces of both the standard polynomial time representation and the tally polynomial time representation of a countably infinite dimensional vector space V∞ over a finite field F. We show that for both the standard and tally representation of V∞, there exists polynomial time subspaces U and W such that U + V is not recursive. We also study the NP analogues of simple and maximal subspaces. We show that the existence of P-simple and NP-maximal subspaces is oracle dependent in both the tally and standard representations of V∞. This contrasts with the case of sets, where the existence of NP-simple sets is oracle dependent but NP-maximal sets do not exist. We also extend many results of Nerode and Remmel concerning the relationship of P bases and NP-subspaces in the tally representation of V∞ to the standard representation of V∞

Download options


    Upload a copy of this work     Papers currently archived: 72,805

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library


Added to PP

6 (#1,142,048)

6 months
1 (#386,031)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations

Similar books and articles

Vector-Spinor Space and Field Equations.Nathan Rosen & Gerald E. Tauber - 1987 - Foundations of Physics 17 (1):63-99.
Polynomial Time Uniform Word Problems.Stanley Burris - 1995 - Mathematical Logic Quarterly 41 (2):173-182.
Decidable Subspaces and Recursively Enumerable Subspaces.C. J. Ash & R. G. Downey - 1984 - Journal of Symbolic Logic 49 (4):1137-1145.
The Theory of {Vec Z}C(2)^2-Lattices is Decidable.Stefano Baratella & Carlo Toffalori - 1998 - Archive for Mathematical Logic 37 (2):91-104.
Simple and Hyperhypersimple Vector Spaces.Allen Retzlaff - 1978 - Journal of Symbolic Logic 43 (2):260-269.
Infinite Substructure Lattices of Models of Peano Arithmetic.James H. Schmerl - 2010 - Journal of Symbolic Logic 75 (4):1366-1382.
Complexity, Decidability and Completeness.Douglas Cenzer & Jeffrey B. Remmel - 2006 - Journal of Symbolic Logic 71 (2):399 - 424.
Extending Independent Sets to Bases and the Axiom of Choice.Kyriakos Keremedis - 1998 - Mathematical Logic Quarterly 44 (1):92-98.