Title:
Gaps in Bounded Query Hierarchies
Please wait while I download
TR98026, Electronic Colloquium on Computational Complexity, 1998.
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_{mtt}^{SAT}
=> P_{btt}^{SAT} = P_{mtt}^{SAT}
and for all sets A

FP_{(m+1)tt}^{A} = FP_{mtt}^{A}
=> FP_{btt}^{A} = FP_{mtt}^{A}

P_{(m+1)T}^{A} = P_{mT}^{A}
=> P_{bT}^{A} = P_{mT}^{A}

FP_{(m+1)T}^{A} = FP_{mT}^{A}
=> FP_{bT}^{A} = FP_{mT}^{A}
where P_{mtt}^{A} is the set of languages computable by polynomialtime
Turing machines that make m nonadaptive queries to A;
P_{btt}^{A} = U_{m} P_{mtt}^{A}; P_{mT}^{A}
and P_{bT}^{A} are
the analogous adaptive queries classes; and
FP_{mtt}^{A}, FP_{btt}^{A}, FP_{mT}^{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_{2mtt}^{A} = P_{mtt}^{A}
=> P_{btt}^{A} = P_{mtt}^{A}.
We disprove the conjecture. In fact,
P_{[4m/3]tt}^{A} = P_{mtt}^{A}
≠> P_{([4m/3]+1)tt}^{A} = P_{[4m/3]tt}^{A}.
Thus there is a P_{mtt}^{A} hierarchy that contains a finite gap.
We also make progress on the 3tt vs. 2tt case:
P_{3tt}^{A} = P_{2tt}^{A}
=> P_{btt}^{A} &sube P_{2tt}^{A}/poly.
Download Full Paper