On computational complexity and honest polynomial degrees

DOI10.1016/0304-3975(91)90354-5zbMath0725.03025OpenAlexW2052608516MaRDI QIDQ2277252

Rodney G. Downey

Publication date: 1991

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

Full work available at URL: https://doi.org/10.1016/0304-3975(91)90354-5

zbMATH Keywords

honest m-degreeshonest polynomial degreepolynomial degrees of low r.e. setstally degrees

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Other degrees and reducibilities in computability and recursion theory (03D30)

Related Items (3)

The structure of the honest polynomial m-degrees ⋮ Strong polynomial-time reducibility ⋮ On \(\Pi_ 2\) theories of \(hp-T\) degrees of low sets

Cites Work

• Honest polynomial time reducibilities and the \(P=?NP\) problem
• Honest polynomial degrees and \(P=?NP\)
• A note on structure and looking back applied to the relative complexity of computable functions
• The structure of the honest polynomial m-degrees
• On the Structure of Polynomial Time Reducibility
• Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
• On complexity properties of recursively enumerable sets
• Computational complexity, speedable and levelable sets
• Computational complexity of recursively enumerable sets
• A Machine-Independent Theory of the Complexity of Recursive Functions
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On computational complexity and honest polynomial degrees