Selectivity: Reductions, Nondeterminism, and Function Classes
Lane A. Hemaspaandra, Albrecht Hoene, Ashish V. Naik, Mitsunori Ogiwara, Alan L. Selman, Thomas Thierauf, Jie Wang · 1993
A set is P-selective [Se179] if there is a polynomial-time semi-decision algorithm or 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 o 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 coNP)/poly, are extended low, and (those in NP) are Low2; we also show that NP-selective sets cannot be NP-complete unless NP = coNP. By studying more general notions o nondeterministic selectivity, we conclude that all multivalued NP functions have single-valued NP refinements only if the polynomial hierarchy collapses to its second level.