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)

Review text

No \(\Delta^ 0_ 2\) set A with \(\bar A\) and A both semilow has a minimal honest polynomial (hp-)degree. The hp-degrees and polynomial degrees of low r.e. sets are dense, showing, for example, that r.e. sets of minimal hp-degree have high computational complexity in Blum-Marques' sense. Similar results can be obtained for tally degrees and polynomial (honest) m-degrees.

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

• 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
• 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?)
• 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)

• Strong minimal pair theorem for the honest polynomial degrees of \(\Delta{}^ 0_ 2\) low sets
• On \(\Pi_ 2\) theories of \(hp-T\) degrees of low sets
• The structure of the honest polynomial m-degrees
• 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)