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

DOI10.1016/0168-0072(95)00051-8zbMath0862.03026OpenAlexW1991499254MaRDI QIDQ1923577

Anil Nerode, Jeffery B. Remmel

Publication date: 25 November 1996

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0168-0072(95)00051-8

zbMATH Keywords

vector spaceoraclessimple setsmaximal setsNP-maximal subspacesP-simple subspacessemilattice of NP vector subspaces

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Theory of numerations, effectively presented structures (03D45)

Cites Work

• Oracle-dependent properties of the lattice of NP sets
• Complexity-theoretic algebra. II: Boolean algebras
• Complexity and structure
• Polynomial-time versus recursive models
• Polynomial-time Abelian groups
• The p-T-degrees of the recursive sets: Lattice embeddings, extensions of embeddings and the two-quantifier theory
• Recursively presented games and strategies
• On splitting recursive sets
• A context for belief revision: forward chaining-normal nonmonotonic rule systems
• Maximal and Cohesive vector spaces
• Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
• Recursion theory on algebraic structures with independent sets
• On r.e. and co-r.e. vector spaces with nonextendible bases
• Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
• Maximal vector spaces under automorphisms of the lattice of recursively enumerable vector spaces
• Recursively enumerable vector spaces
• Recursively enumerable Boolean algebras
• Feasible Graphs and Colorings
• Reducibility among Combinatorial Problems
• On the Computational Complexity of Algorithms
• Paths, Trees, and Flowers
• Classes of Recursively Enumerable Sets and Degrees of Unsolvability
• Two notes on vector spaces with recursive operations
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item