L. Hemaspaandra, A. Hoene, A. Naik, M Ogihara, A. Selman, T. Thierauf, and J. Wang
Abstract:
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.