The structure of the honest polynomial m-degrees
From MaRDI portal
Publication:1341316
DOI10.1016/0168-0072(94)90027-2zbMath0818.03020OpenAlexW2061045889MaRDI QIDQ1341316
Michael Moses, William I. Gasarch, Rodney G. Downey
Publication date: 9 January 1995
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(94)90027-2
Complexity of computation (including implicit computational complexity) (03D15) Recursively (computably) enumerable sets and degrees (03D25) Other degrees and reducibilities in computability and recursion theory (03D30)
Related Items
Query-monotonic Turing reductions ⋮ The theory of the polynomial many-one degrees of recursive sets is undecidable ⋮ On computational complexity and honest polynomial degrees
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On degrees of recursive unsolvability
- A low and a high hierarchy within NP
- Honest polynomial degrees and \(P=?NP\)
- Structure of the upper semilattice of recursively enumerable m-degrees and related questions. I
- On the structure of sets in NP and other complexity classes
- Two theorems on many-one degrees of recursively enumerable sets
- A comparison of polynomial time reducibilities
- On the density of honest subrecursive classes
- Classical recursion theory. Vol. II
- On computational complexity and honest polynomial degrees
- Initial segments of the degrees of unsolvability
- Sublattices of the polynomial time degrees
- A minimal degree less than 0’
- Minimal degrees for polynomial reducibilities
- Strong reducibilities
- On the Structure of Polynomial Time Reducibility
- Recursively enumerable sets and degrees
- Distributive Initial Segments of the Degrees of Unsolvability
- Initial Segments of Many-One Degrees
- A Classification of the Recursive Functions
