On computational complexity and honest polynomial degrees

DOI10.1016/0304-3975(91)90354-5MaRDI QIDQ2277252zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• The structure of the honest polynomial m-degrees
• Strong minimal pair theorem for the honest polynomial degrees of \(\Delta{}^ 0_ 2\) low sets
• Honest polynomial degrees and \(P=?NP\)
• scientific article; zbMATH DE number 922628
• Minimal degrees for polynomial reducibilities

Cites work

• scientific article; zbMATH DE number 4131660 (Why is no real title available?)
• scientific article; zbMATH DE number 3861137 (Why is no real title available?)
• scientific article; zbMATH DE number 3930984 (Why is no real title available?)
• scientific article; zbMATH DE number 4007728 (Why is no real title available?)
• scientific article; zbMATH DE number 4091484 (Why is no real title available?)
• scientific article; zbMATH DE number 3291134 (Why is no real title available?)
• A Machine-Independent Theory of the Complexity of Recursive Functions
• A note on structure and looking back applied to the relative complexity of computable functions
• Computational complexity of recursively enumerable sets
• Computational complexity, speedable and levelable sets
• Honest polynomial degrees and \(P=?NP\)
• Honest polynomial time reducibilities and the \(P=?NP\) problem
• On complexity properties of recursively enumerable sets
• On the Structure of Polynomial Time Reducibility
• Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
• The structure of the honest polynomial m-degrees

Cited in

(4)

• On \(\Pi_ 2\) theories of \(hp-T\) degrees of low sets
• The structure of the honest polynomial m-degrees
• Strong minimal pair theorem for the honest polynomial degrees of \(\Delta{}^ 0_ 2\) low sets
• Strong polynomial-time reducibility

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2277252)