Show simple item record

dc.contributor.authorChang, Richarden_US
dc.date.accessioned2007-04-23T17:34:55Z
dc.date.available2007-04-23T17:34:55Z
dc.date.issued1988-11en_US
dc.identifier.citationhttp://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR88-944en_US
dc.identifier.urihttps://hdl.handle.net/1813/6784
dc.description.abstractIn [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}$.en_US
dc.format.extent1170749 bytes
dc.format.extent299887 bytes
dc.format.mimetypeapplication/pdf
dc.format.mimetypeapplication/postscript
dc.language.isoen_USen_US
dc.publisherCornell Universityen_US
dc.subjectcomputer scienceen_US
dc.subjecttechnical reporten_US
dc.titleOn the Structure of Bounded Queries to Arbitrary NP Setsen_US
dc.typetechnical reporten_US


Files in this item

Thumbnail
Thumbnail

This item appears in the following Collection(s)

Show simple item record

Statistics