Minimal degrees for polynomial reducibilities

Reviewer: Eric Warren Allender

Complexity theoreticians have a recurring dream: that techniques of recursion theory will lead to a resolution of the P vs. NP problem. This paper gives tantalizing hints that this dream might not be in vain; the author shows that either P ? NP or the degree structure of the recursive sets is very different from that of the nonrecursive sets. This is one of the few cases in which questions about nonrecursive sets have been shown to bear upon complexity-theoretic issues. A set C is minimal if it is not in P, but every set reducible to C is either in P or is equivalent to C. Homer first considers the usual polynomial-time Turing and many-one reducibilities, and extends Ladner's Theorem to show that there is no minimal degree with respect to these reducibilities. (I.e., if C is a set not in P, then there is a set A ? :.KC# /P such that A is reducible to C, but C is not reducible to A; thus A is “easier” than C.) Next, the author considers “honest” reductions, which, on input x, ask questions only about strings of approximately the same size as x. Honest reductions have been considered previously by other authors. Again, Ladner's Theorem shows that if C is recursive, then C is not minimal with respect to honest reductions. Homer's main result, which is very surprising, is that Ladner's Theorem cannot be extended to nonrecursive sets without first proving P ? NP; i.e., if P = NP, then there are minimal sets with respect to honest reductions. The paper is well written. Readers should note that a much simpler proof of the main result (Theorem 3) may be found in [1]. A stronger version of the result is proved in [2].