Please use this identifier to cite or link to this item: http://hdl.handle.net/1813/6682
 Title: Is One NP Question as Powerful as Two? Authors: Kadin, Jim Keywords: computer sciencetechnical report Issue Date: Jun-1987 Publisher: Cornell University Citation: http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR87-842 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. URI: http://hdl.handle.net/1813/6682 Appears in Collections: Computer Science Technical Reports

Files in This Item:

File Description SizeFormat