The p-T-degrees of the recursive sets: Lattice embeddings, extensions of embeddings and the two-quantifier theory

DOI10.1016/0304-3975(92)90078-TzbMath0774.03028MaRDI QIDQ1193873

Theodore A. Slaman, Richard A. Shore

Publication date: 27 September 1992

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

embedding problemdensityrecursive latticenonhomogeneity\(p\)- time degrees\(p\)-time many-one degreespolynomial-time Turing degrees of the recursive setstwo-quantifier theory

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Other degrees and reducibilities in computability and recursion theory (03D30)

Related Items

On MODkP Counting Degrees, On the lattices of NP-subspaces of a polynomial time vector space over a finite field, The theory of the polynomial many-one degrees of recursive sets is undecidable, Decidability of the two-quantifier theory of the recursively enumerable weak truth-table degrees and other distributive upper semi-lattices, Strong polynomial-time reducibility, Nondiamond theorems for polynomial time reducibility, Differences between resource bounded degree structures, Lattice representations for computability theory, On \(\Pi_ 2\) theories of \(hp-T\) degrees of low sets

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On degrees of recursive unsolvability
• Density of a final segment of the truth-table degrees
• Oracle-dependent properties of the lattice of NP sets
• Minimal pairs for P
• Every finite lattice can be embedded in a finite partition lattice
• A note on structure and looking back applied to the relative complexity of computable functions
• On the structure of sets in NP and other complexity classes
• A uniform approach to obtain diagonal sets in complexity classes
• Diagonalization, uniformity, and fixed-point theorems
• A comparison of polynomial time reducibilities
• Polynomial and abstract subrecursive classes
• Initial segments of the degrees of size \(\aleph _ 1\)
• Initial segments of the degrees of unsolvability
• The upper semi-lattice of degrees of recursive unsolvability
• Sublattices of the polynomial time degrees
• Decidability and Invariant Classes for Degree Structures
• Finitely Generated Codings and the Degrees R.E. in a Degree d
• On the Structure of Polynomial Time Reducibility
• Countable initial segments of the degrees of unsolvability
• Distributive Initial Segments of the Degrees of Unsolvability
• The complexity of theorem-proving procedures