Honest polynomial time reducibilities and the \(P=?NP\) problem (Q909455)

Assuming \(P\neq NP\), the author shows that the honest polynomial time reducibilities differ from their nonhonest counterparts on the NP sets. The degree-invariant properties of such honest reducibilities are then investigated. By extending a result of Homer, it is shown that \(P=NP\) implies the existence of a recursively enumerable set A which is minimal for the honest polynomial reducibilities. This shows that \(P\neq NP\) if the degree structures of honest and nonhonest reducibilities on the r.e. sets are isomorphic.