Cornell University
Library
Cornell UniversityLibrary

eCommons

Help
Log In(current)
  1. Home
  2. Cornell Computing and Information Science
  3. Computer Science
  4. Computer Science Technical Reports
  5. Is One NP Question as Powerful as Two?

Is One NP Question as Powerful as Two?

File(s)
87-842.ps (354.55 KB)
87-842.pdf (1.9 MB)
Permanent Link(s)
https://hdl.handle.net/1813/6682
Collections
Computer Science Technical Reports
Author
Kadin, Jim
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.

Date Issued
1987-06
Publisher
Cornell University
Keywords
computer science
•
technical report
Previously Published as
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR87-842
Type
technical report

Site Statistics | Help

About eCommons | Policies | Terms of use | Contact Us

copyright © 2002-2026 Cornell University Library | Privacy | Web Accessibility Assistance