{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,19]],"date-time":"2025-03-19T12:10:39Z","timestamp":1742386239763},"reference-count":0,"publisher":"World Scientific Pub Co Pte Lt","issue":"04","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[1995,12]]},"abstract":"<jats:p> In this note, we study NP-selective sets (formally, sets that are selective via NPSV <jats:sub>t<\/jats:sub> functions) as a natural generalization of P-selective sets. We show that, assuming P\u2260NP\u2229coNP , 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 \u201crelativization technique,\u201d by using the known properties of P-selective sets. Using this technique, we strengthen a result of Longpr\u00e9 and Selman on hard promise problems and show that the result \u201c NP \u2286( NP \u2229 coNP )\/ poly \u21d2 PH=NP <jats:sup> NP <\/jats:sup>\u201d is implicit in Karp and Lipton\u2019s seminal result on nonuniform classes. <\/jats:p>","DOI":"10.1142\/s0129054195000214","type":"journal-article","created":{"date-parts":[[2004,11,12]],"date-time":"2004-11-12T06:59:25Z","timestamp":1100242765000},"page":"403-416","source":"Crossref","is-referenced-by-count":19,"title":["NONDETERMINISTICALLY SELECTIVE SETS"],"prefix":"10.1142","volume":"06","author":[{"given":"LANE A.","family":"HEMASPAANDRA","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"ALBRECHT","family":"HOENE","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"ASHISH V.","family":"NAIK","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"MITSUNORI","family":"OGIHARA","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"ALAN L.","family":"SELMAN","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"THOMAS","family":"THIERAUF","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"JIE","family":"WANG","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054195000214","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T11:31:06Z","timestamp":1565177466000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054195000214"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,12]]},"references-count":0,"journal-issue":{"issue":"04","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[1995,12]]}},"alternative-id":["10.1142\/S0129054195000214"],"URL":"https:\/\/doi.org\/10.1142\/s0129054195000214","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995,12]]}}}