Authors: Richard Beigel
Abstract: We study the complexity of decision problems that can be solved by a polynomial-time Turing machine that makes a bounded number of queries to an NP oracle. Depending on whether we allow some queries to depend on the results of other queries, we obtain two (probably) different hierarchies. We present several results relating the bounded NP query hierarchies to each other and to the Boolean hierarchy. We also consider the similarly-defined hierarchies of functions that can be computed by a polynomial-time Turing machine that makes a bounded number of queries to an NP oracle. We present relations among these two hierarchies and the Boolean hierarchy.
In particular we show for all k that there are functions computable with 2k parallel queries to an NP set that are not computable in polynomial time with k serial queries to any oracle, unless P = NP. As a corollary k + 1 parallel queries to an NP set allow us to compute more functions than are computable with only k parallel queries to an NP set, unless P = NP; the same is true of serial queries. Similar results hold for all tt-self-reducible sets.
Using a ``mind-change'' technique, we show that
In addition we show that the Boolean hierarchy and the bounded query
hierarchies (of languages) either stand or collapse together. Finally
we show that if the Boolean hierarchy collapses to any level but the
zeroth (deterministic polynomial time), then for all k there are
functions computable in polynomial time with k parallel queries to
an NP set that are not computable in polynomial time with
Download Full Paper