The structure of the honest polynomial m-degrees

DOI10.1016/0168-0072(94)90027-2zbMath0818.03020MaRDI 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

zbMATH Keywords

initial segment; tally sets; honest m-reduction; honest polynomial m-degrees; P\(=\)NP

Mathematics Subject Classification ID

03D15: Complexity of computation (including implicit computational complexity)

03D25: Recursively (computably) enumerable sets and degrees

03D30: Other degrees and reducibilities in computability and recursion theory

Related Items

The theory of the polynomial many-one degrees of recursive sets is undecidable, On computational complexity and honest polynomial degrees, Query-monotonic Turing reductions

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