Title: Gaps in Bounded Query Hierarchies

in the 14th Annual Conference on Computational Complexity, pp. 124-141, 1999

Author: Richard Beigel

Abstract: Prior results show that most bounded query hierarchies cannot contain finite gaps. For example, it is known that

P(m+1)-ttSAT = Pm-ttSAT => PbttSAT = Pm-ttSAT
and for all sets A where Pm-ttA is the set of languages computable by polynomial-time Turing machines that make m nonadaptive queries to A; PbttA = Um Pm-ttA; Pm-TA and PbTA are the analogous adaptive queries classes; and FPm-ttA, FPbttA, FPm-TA, and FPbTA in turn are the analogous function classes.

It was widely expected that these general results would extend to the remaining case -- languages computed with nonadaptive queries -- yet results remained elusive. The best known was that

P2m-ttA = Pm-ttA => PbttA = Pm-ttA.
We disprove the conjecture. In fact,
P[4m/3]-ttA = Pm-ttA ≠> P([4m/3]+1)-ttA = P[4m/3]-ttA.
Thus there is a Pm-ttA hierarchy that contains a finite gap.

We also make progress on the 3-tt vs. 2-tt case:

P3-ttA = P2-ttA => PbttA &sube P2-ttA/poly.

Download Extended Abstract