Minimal Degrees For Honest Polynomial Reducibilities
Steven Thomas Homer · 1984
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 [L] whew reciirsive sets are considered. An "honest" polynomial reducibility, ⩽is defined which is a strengthening of polynomial Turing reducibility. We prove that no recursive set, (or igeeand P-immune set) has minimalssets (or even all 3 sets) would imply P 2 .y/l. Finally, a partial converse of this result is obtained, proving that if a certain class of one-way functions exists then no set has minimal (h/t)-degree.