**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 2^{k} 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 ^{k} - 1*k* serial
queries to an NP set. (In fact, the same is true for any class in
place of NP that is closed under polynomial-time
positive-bounded-truth-table reductions.) This contrasts with the
expected result for function computations with an NP oracle
(Beigel, Johns Hopkins University TR-04, 1988).

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 *k* - 1