Honest polynomial degrees and P=?NP

DOI10.1016/0304-3975(87)90036-3zbMATH Open0631.68048OpenAlexW2089252442MaRDI QIDQ1094875FDOQ1094875

S. Homer, Timothy J. Long

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)

Cites Work

• On the Structure of Polynomial Time Reducibility
• Title not available (Why is that?)
• Title not available (Why is that?)
• On degrees of recursive unsolvability
• On some natural complete operators
• Minimal degrees for polynomial reducibilities
• A uniform approach to obtain diagonal sets in complexity classes
• Title not available (Why is that?)

Cited In (6)

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

   Recommendations

• Title not available (Why is that?) 👍 👎
• Honest polynomial time reducibilities and the \(P=?NP\) problem 👍 👎
• Minimal degrees for polynomial reducibilities 👍 👎
• The structure of the honest polynomial m-degrees 👍 👎
• Title not available (Why is that?) 👍 👎

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)