On honest polynomial reductions, relativizations, and P=NP
Rodney G. Downey, Steven Thomas Homer, William I. Gasarch, Michael F. Moses · 2003
The authors prove a number of structural theorems about the honest polynomial m-degrees, contingent on the assumption P=NP (or a unary alphabet). The ultimate goal would be to prove a contradiction from P=NP. They show that low sets cannot be minimal with respect. They also show that some theorems about honest polynomial reductions do not relativize; hence, techniques in this area may be able to resolve the P=NP question. They examine an alternative definition of honest m-reduction under which recursive minimal sets can be constructed.>