Honest polynomial time reducibilities and the P=?NP problem

摘要

We study the honest versions of polynomial time bounded many-one and Turing reducibility. We show that, assuming P ≠ NP, the honest polynomial time reducibilities differ from their nonhonest counterparts on the NP-sets. We then investigate degree invariant properties of the honest reducibilities. By extending a result of Homer (in “Proceedings, 25th IEEE Sympos. Found. Comput. Sci., 1984”), we show that P = NP implies the existence of a recursively enumerable set A which is minimal for the honest polynomial reducibilities, i.e., A is not polynomial time computable and any set B which reduces to A is either polynomial time computable or equivalent to A. Since there are no minimal sets for the general polynomial time reducibilities, this shows that P ≠ NP if the degree structures of the honest and nonhonest reducibilities on the recursively enumerable sets are isomorphic. Finally, by studying a notion related to minimality, we obtain a similar result for recursive sets too.