NONDETERMINISTICALLY SELECTIVE SETS
Lane A. Hemaspaandra, Albrecht Hoene, Ashish V. Naik, Mitsunori Ogihara, Alan L. Selman, Thomas Thierauf, Jie Wang · International Journal of Foundations of Computer Science · 1995
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≠NP∩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é and Selman on hard promise problems and show that the result “ NP ⊆( NP ∩ coNP )/ poly ⇒ PH=NP NP ” is implicit in Karp and Lipton’s seminal result on nonuniform classes.