Honest polynomial degrees and P=? NP
Steven Thomas Homer, Timothy J. Long · Theoretical Computer Science · 1987
We present a relatively simple proof of a result from Homer (1986) showing that if nonrecursive sets cannot be minimal for honest polynomial-time Turing reducibility (⩽ h T -minimal), then P ≠ NP . As a corollary to our proof, we strengthen Homer's result by showing, without assuming that P ≠ NP , that there are ⩽ h T -minimal sets for all tally sets. We also consider the converse of Homer's result, providing some evidence that the nonexistence of ⩽ h T -minimal sets may folow from P ≠ NP in an interesting way. Finally, we consider structural and/or computability properties of sets that cannot be ⩽ h T -minimal.