Polynomial Time Enumeration Reducibility
Alan L. Selman · SIAM Journal on Computing · 1978
A viable polynomial time enumeration reducibility is defined and studied. Let $ \leqq _{{\text{pe}}} $ denote this reducibility. $ \leqq _{{\text{pe}}} $ is intrinsic to certain tradeoffs between nondeterministic oracle recognition of sets and deterministic oracle computations between functions. A set belongs to $\mathcal{NP}$ if and only if the set is, in some natural sense, polynomial enumerable. $ \leqq _{{\text{pe}}} $ is defined so that $A \leqq _{{\text{pe}}} B$ just in case for every set C, every polynomial enumeration of B relative to C yields some polynomial enumeration of A relative to C. Various properties of $ \leqq _{{\text{pe}}} $ are shown. In particular, $ \leqq _{{\text{pe}}} $ is a maximal transitive subrelation of $ \leqq _{\text{T}}^{\mathcal{NP}} $. Also, $ \leqq _{{\text{pe}}} $ is equal to $ \leqq _{\text{c}}^{\mathcal{NP}} $ on low level complexity classes, but the equality does not hold over all recursive sets.