### Minimal degrees for polynomial reducibilitiesMinimal degrees for polynomial reducibilities

Access Restriction
Subscribed

 Author Homer, Steven Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©1987 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Abstract 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 $≤\textit{h}\textit{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 ≤ $\textit{h}\textit{T}$ degree. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 1987-04-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 34 Issue Number 2 Page Count 12 Starting Page 480 Ending Page 491

#### Open content in new tab

Source: ACM Digital Library