Minimal degrees for polynomial reducibilities
Steven Thomas Homer · Journal of the ACM · 1987
The existence of minimal degrees is investigated for several polynomial reducibilities. It is shown that no set has minimal degree with respect to polynomial many-one or Turing reducibility. This extends a result of Ladner in which only recursive sets are considered. A polynomial reducibility ≤ h T is defined. This reducibility is a strengthening of polynomial Turing reducibility, and its properties relate to the P = ? NP question. For this new reducibility, a set of minimal degree is constructed under the assumption that P = NP. However, the set constructed is nonrecursive, and it is shown that no recursive set is of minimal ≤ h T degree.