Selectivity: Reductions, Nondeterminism, and Function Classes

L. Hemaspaandra, A. Hoene, A. Naik, M Ogihara, A. Selman, T. Thierauf, and J. Wang

In this note, we study NP-selective sets (formally, sets that are selective via NPSV_t functions) as a natural generalization of P-selective sets. We show that, assuming P different from NP intersect coNP, the class of NP-selective sets properly contains the class of P-selective sets. We study several properties of NP-selective sets such as self-reducibility, hardness under various reductions, lowness, and nonuniform complexity. We prove many of our results via a ``relativization technique,'' by using the known properties of P-selective sets. Using this technique, we strengthen a result of Longpr\'e and Selman on hard promise problems and show that the result ``NP in (NP intersect coNP)/\poly implies PH = NP^NP'' is implicit in Karp and Lipton's seminal result on nonuniform classes.