{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:29:10Z","timestamp":1787340550849,"version":"build-2736575974"},"reference-count":16,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1985,8]]},"abstract":"<jats:p>A restricted relativization of NP, denoted ${\\text{NP}}_B ( \\cdot )$,was introduced in [SIAM J. Comput., 13 (1984), pp. 461\u2013 487] in the study of positive relativizations on the ${\\text{P}} = ?{\\text{ NP}}$ question. The ${\\text{NP}}_B ( \\cdot )$ restriction allows nondeterministic polynomial-time oracle machines to query only polynomially many strings in its computation trees. In this paper we compare the language classes ${\\text{NP}}_B (A)$, relative to arbitrary sets A, with the language classes $\\text{NP}(S)$, relative to sparse sets S, showing that it is not always possible to obtain a class specified by ${\\text{NP}}_B (A)$ as an $\\text{NP}(S)$ class and vice versa. As a corollary to these results, we prove that there is a sparse set S such that for all tally sets T, $S \\not\\equiv_T^{\\text{SN}} T$. This implies that the relationship established in [5] that for every sparse set S there is a tally set T such that $S \\equiv _T^{\\text{NP}} T$ cannot be improved to any of the strong nondeterministic polynomial-time degrees. Finally, we strengthen a result appearing in [4] by showing that nondeterministic oracle programs for sets $B \\in \\Sigma _k^{\\text{P}} - \\Delta _k^{\\text{P}} $, for $k \\geqq 2$, must search through exponentially many strings (infinitely often) that are actually in the oracle set when using oracle sets from $\\Sigma _{k - 1}^{\\text{P}} $. As a consequence, sparse sets at some $\\Sigma^{\\text{P}} $ level of the polynomial-time hierarchy cannot be used as orcales for sets properly at the next $\\Sigma^{\\text{P}} $ level.<\/jats:p>","DOI":"10.1137\/0214043","type":"journal-article","created":{"date-parts":[[2005,2,24]],"date-time":"2005-02-24T06:25:35Z","timestamp":1109226335000},"page":"585-597","source":"Crossref","is-referenced-by-count":31,"title":["On Restricting the Size of Oracles Compared with Restricting Access to Oracles"],"prefix":"10.1137","volume":"14","author":[{"given":"Timothy J.","family":"Long","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,8,2]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1137\/0204037"},{"key":"R2","unstructured":"J. Balc\u00e1zar, R. Book, U. Sch\u00f6ning,  The polynomial-time hierarchy, sparse oracles, and lowness,  1983, manuscript"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1137\/0206023"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1137\/0213030"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(83)90024-8"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(82)90382-5"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(75)90016-X"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(82)90085-8"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1145\/5925.5938"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(82)90002-2"},{"key":"R12","unstructured":"S. Mahaney, J. Simon,  On sparse sets in PTAPE, manuscript"},{"key":"R13","doi-asserted-by":"crossref","unstructured":"A. Meyer, L. Stockmeyer,  the equivalence of regular expressions with squaring requires exponential space,  Proc. 13th IEEE SWAT,  1972,  125\u2013129","DOI":"10.1109\/SWAT.1972.29"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1137\/0207035"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(76)90061-X"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(76)90062-1"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/0214043","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:39:08Z","timestamp":1787337548000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/0214043"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1985,8]]},"references-count":16,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1985,8]]}},"alternative-id":["10.1137\/0214043"],"URL":"https:\/\/doi.org\/10.1137\/0214043","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1985,8]]}}}