Honest polynomial degrees and P=?NP

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

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

honest Turing machineminimal setsnonrecursive setsoracle Turing machinereducible setstally set

Mathematics Subject Classification ID

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

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

• A uniform approach to obtain diagonal sets in complexity classes
• 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?)
• 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)

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

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)