On computational complexity and honest polynomial degrees

DOI10.1016/0304-3975(91)90354-5zbMATH Open0725.03025OpenAlexW2052608516MaRDI QIDQ2277252FDOQ2277252

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

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

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)

Cites Work

• On the Structure of Polynomial Time Reducibility
• Title not available (Why is that?)
• Title not available (Why is that?)
• A Machine-Independent Theory of the Complexity of Recursive Functions
• Title not available (Why is that?)
• Title not available (Why is that?)
• Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
• Honest polynomial time reducibilities and the \(P=?NP\) problem
• Computational complexity, speedable and levelable sets
• Honest polynomial degrees and \(P=?NP\)
• A note on structure and looking back applied to the relative complexity of computable functions
• Title not available (Why is that?)
• Title not available (Why is that?)
• On complexity properties of recursively enumerable sets
• Computational complexity of recursively enumerable sets
• 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)