On Restricting the Size of Oracles Compared with Restricting Access to Oracles

A restricted relativization of NP, denoted ${\text{NP}}_B ( \cdot )$,was introduced in [SIAM J. Comput., 13 (1984), pp. 461– 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 polyn...