Complexity-theoretic algebra. II: Boolean algebras

DOI10.1016/0168-0072(89)90047-XzbMath0703.03023OpenAlexW2013547557MaRDI QIDQ915723

Anil Nerode, Jeffery B. Remmel

Publication date: 1989

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(89)90047-x

zbMATH Keywords

decidable theoriesoraclescomplexity of constructions of idealscountable atomless Boolean algebramaximal recursive idealsrecursive idealsrecursively axiomatizable complete theoriesrecursively axiomatizable theoriesRecursively enumerable ideals

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computable structure theory, computable model theory (03C57) Theory of numerations, effectively presented structures (03D45)

Related Items

A theory of nonmonotonic rule systems I, On the lattices of NP-subspaces of a polynomial time vector space over a finite field, Complexity and categoricity, Feasibly categorical models, Polynomial-time axioms of choice and polynomial-time cardinality, Polynomial-time versus recursive models, Space complexity of abelian groups, Complexity, decidability and completeness, Feasible graphs with standard universe

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Oracle-dependent properties of the lattice of NP sets
• Complexity and structure
• On splitting recursive sets
• A context for belief revision: forward chaining-normal nonmonotonic rule systems
• Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
• Effective content of field theory
• 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
• Reducibility among Combinatorial Problems
• On the Computational Complexity of Algorithms
• Paths, Trees, and Flowers
• Classes of Recursively Enumerable Sets and Degrees of Unsolvability
• The complexity of theorem-proving procedures
• Two notes on vector spaces with recursive operations