Gaps in Bounded Query Hierarchies
Please wait while I download
TR98-026, Electronic Colloquium on Computational Complexity, 1998.
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.
FP(m+1)-ttA = FPm-ttA
=> FPbttA = FPm-ttA
P(m+1)-TA = Pm-TA
=> PbTA = Pm-TA
FP(m+1)-TA = FPm-TA
=> FPbTA = FPm-TA
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 Full Paper