Honest polynomial degrees and P=? NP

AbstractWe 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 (⩽hT-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 ⩽hT-minimal sets for all tally sets. We also consider the converse of Homer's result, providing some evidence that the nonexistence of ⩽hT-minimal sets may folow from P ≠ NP in an interesting way. Finally, we consider structural and/or computability properties of sets that cannot be ⩽hT-minimal