dc.contributor.author Chang, Richard en_US dc.date.accessioned 2007-04-23T17:34:55Z dc.date.available 2007-04-23T17:34:55Z dc.date.issued 1988-11 en_US dc.identifier.citation http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR88-944 en_US dc.identifier.uri https://hdl.handle.net/1813/6784 dc.description.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}$. en_US dc.format.extent 1170749 bytes dc.format.extent 299887 bytes dc.format.mimetype application/pdf dc.format.mimetype application/postscript dc.language.iso en_US en_US dc.publisher Cornell University en_US dc.subject computer science en_US dc.subject technical report en_US dc.title On the Structure of Bounded Queries to Arbitrary NP Sets en_US dc.type technical report en_US
﻿