Honest polynomial degrees and P=?NP

DOI10.1016/0304-3975(87)90036-3MaRDI QIDQ1094875zbMATHOpenAlexFDO

Authors Timothy J. Long, S. Homer

Publication date 1987

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

Full work available at URL https://doi.org/10.1016/0304-3975(87)90036-3

zbMATH Keywords

oracle Turing machineminimal setsnonrecursive setstally sethonest Turing machinereducible sets

Mathematics Subject Classification ID

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

Recommendations

• Publication:5753945
• Honest polynomial time reducibilities and the \(P=?NP\) problem
• Minimal degrees for polynomial reducibilities
• The structure of the honest polynomial m-degrees
• scientific article; zbMATH DE number 4075037

Cites work

• scientific article; zbMATH DE number 3930984 (Why is no real title available?)
• scientific article; zbMATH DE number 3586480 (Why is no real title available?)
• scientific article; zbMATH DE number 3291134 (Why is no real title available?)
• A uniform approach to obtain diagonal sets in complexity classes
• Minimal degrees for polynomial reducibilities
• On degrees of recursive unsolvability
• On some natural complete operators
• On the Structure of Polynomial Time Reducibility

Cited in

(9)

• scientific article; zbMATH DE number 4189714 (Why is no real title available?)
• scientific article; zbMATH DE number 62443 (Why is no real title available?)
• Honest polynomial time reducibilities and the \(P=?NP\) problem
• Cook reducibility is faster than Karp reducibility in NP
• On computational complexity and honest polynomial degrees
• Minimal degrees for polynomial reducibilities
• On \(\Pi_ 2\) theories of \(hp-T\) degrees of low sets
• The existence of minimal honest polynomial degree below and recursively enumerable degrees
• The structure of the honest polynomial m-degrees

This page was built for publication: Honest polynomial degrees and \(P=?NP\)

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