BOUNDED QUERIES TO SAT AND THE BOOLEAN HIERARCHY

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 2k - 1 parallel queries to an NP set allow us to accept in polynomial time exactly the same sets as can be accepted in polynomial time with 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, 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 serial queries to any set (NP-complete sets are p-superterse).