Honest polynomial degrees and \(P=?NP\)

DOI10.1016/0304-3975(87)90036-3zbMath0631.68048OpenAlexW2089252442MaRDI QIDQ1094875

Timothy J. Long, Homer, Steven

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)

Related Items

The structure of the honest polynomial m-degrees ⋮ Honest polynomial time reducibilities and the \(P=?NP\) problem ⋮ On computational complexity and honest polynomial degrees ⋮ Cook reducibility is faster than Karp reducibility in NP ⋮ On \(\Pi_ 2\) theories of \(hp-T\) degrees of low sets

Cites Work

• On degrees of recursive unsolvability
• On some natural complete operators
• A uniform approach to obtain diagonal sets in complexity classes
• Minimal degrees for polynomial reducibilities
• On the Structure of Polynomial Time Reducibility
• Unnamed Item
• Unnamed Item
• Unnamed Item