Gaps in Bounded Query Hierarchies

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)-tt^SAT = P_m-tt^SAT => P_btt^SAT = P_m-tt^SAT and for all sets A

FP_(m+1)-tt^A = FP_m-tt^A => FP_btt^A = FP_m-tt^A
P_(m+1)-T^A = P_m-T^A => P_bT^A = P_m-T^A
FP_(m+1)-T^A = FP_m-T^A => FP_bT^A = FP_m-T^A

where P_m-tt^A is the set of languages computable by polynomial-time Turing machines that make m nonadaptive queries to A; P_btt^A = U_m P_m-tt^A; P_m-T^A and P_bT^A are the analogous adaptive queries classes; and FP_m-tt^A, FP_btt^A, FP_m-T^A, and FP_bT^A 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

P_2m-tt^A = P_m-tt^A => P_btt^A = P_m-tt^A. We disprove the conjecture. In fact, P_[4m/3]-tt^A = P_m-tt^A ≠> P_{([4m/3]+1)-tt}^A = P_[4m/3]-tt^A. Thus there is a P_m-tt^A hierarchy that contains a finite gap.

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

P_3-tt^A = P_2-tt^A => P_btt^A &sube P_2-tt^A/poly.

Download Extended Abstract