Selectivity: Reductions, Nondeterminism, and Function Classes

A set is P-selective if there is a polynomial-time semi-decision algorithm for the set---an algorithm that given any two strings decides which is ``more likely'' to be in the set. This paper studies two natural generalizations of P-selectivity: the NP-selective sets and the sets reducible or equivalent to P-selective sets via polynomial-time reductions. We establish a strict hierarchy among the various reductions and equivalences to P-selective sets. We show that the NP-selective sets are in (NP \cap coNP)/poly, are extended low, and (those in NP) are Low_2; we also show that NP-selective sets cannot be NP-complete unless NP = coNP. By studying more general notions of nondeterministic selectivity, we conclude that all multivalued NP functions have single-valued NP refinements only if the polynomial hierarchy collapses to its second level