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. On the Structure of Bounded Queries to Arbitrary NP Sets

On the Structure of Bounded Queries to Arbitrary NP Sets

File(s)
88-944.pdf (1.12 MB)
88-944.ps (292.86 KB)
Permanent Link(s)
https://hdl.handle.net/1813/6784
Collections
Computer Science Technical Reports
Author
Chang, Richard
Abstract

In [Kad87b], Kadin showed that if the Polynomial Hierarchy (PH) has infinitely many levels, then for all $k$, $P^{SAT[k]} \subseteq P^{SAT[k+1]}$. In this paper, we extend Kadin's technique to show that a proper query hierarchy is not an exclusive property of SAT. In fact, for any $A \in NP - \overbrace{low_{3}}$, if PH is infinite, then $P^{A[k]} \subseteq P^{A[k+1]}$. Moreover, for the case of parallel queries, we show that $P^{A||[k+1]}$ is not contained in $P^{SAT||[k]}$. We claim that having a proper query hierarchy is a consequence of the oracle access mechanism and not a result of the "hardness" of a set. To support this claim, we show that assuming PH is infinite, one can construct an intermediate set $B \in NP$ so that $P^{B[k+1]} \subseteq P^{SAT[k]}$. That is, the query hierarchy for $B$ grows as "tall" as the query hierarchy for SAT. In addition, $B$ is intermediate, so it is not "hard" in any sense (e.g., not NP hard under many-one, Turing, or strong nondeterministic reductions). Using these same techniques, we explore some other questions about query hierarchies. For example, we show that is there exists any $A$ such that $P^{A[2]} = P^{SAT[1]}$ then PH collapses to $\Delta^{P}_{3}$.

Date Issued
1988-11
Publisher
Cornell University
Keywords
computer science
•
technical report
Previously Published as
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR88-944
Type
technical report

Site Statistics | Help

About eCommons | Policies | Terms of use | Contact Us

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