Is One NP Question as Powerful as Two?

Abstract

For any integer $k$, $P^{SAT[k]}$ is the class of languages accepted by deterministic polynomial time oracle machines that make at most $k$ queries to an oracle for SAT. It is easy to see that $P^{SAT[1]} \subseteq D^{P} \subseteq P^{SAT[2]}$. We use a technique called oracle replacement to show that if $D^{P}$ = co-$D^{P}$, then there is a sparse set $S$ such that $\overline{SAT} \in NP^{S}$ , there exist "small" NP machines that recognize initial segments of $\overline{SAT}$, and the polynomial time hierarchy (PH) is contained in $\Delta^{3}_{P}$. Thus for deterministic polynomial time oracle machines, if one NP question is as powerful as two, then the PH collapses to $\Delta^{3}_{P}$. As another application of oracle replacement, we show that if there exists a sparse set $S \in NP^{SAT}$ such that $\overline{SAT} \in NP^{S}$, then $PH \subseteq \Delta^{3}_{P}$. We also discuss how oracle replacement is a unifying principle for many of the results concerning sparse oracles for NP.