Strong nondeterministic polynomial-time reducibilities

AbstractBuilding on the work of Adleman and Manders [1], we define a new class of reducibilities, the strong nondeterministic polynomial-time reducibilities. We show that several reducibilities in this class differ over the recursive sets and assuming NP ≠ coNP, that they each determine different classes of NP-hard sets. Comparisons in strength are also made between the strong nondeterministic polynomial-time reducibilities and the classes of deterministic and non-deterministic polynomial-time reducibilities in Ladner, Lynch and Selman [6]