Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR98-026 | 5th May 1998 00:00

Gaps in Bounded Query Hierarchies

RSS-Feed

Abstract:

<html>
Prior results show that most bounded query hierarchies cannot
contain finite gaps. For example, it is known that
<center>
P<sub>(<i>m</i>+1)-tt</sub><sup>SAT</sup> = P<sub><i>m</i>-tt</sub><sup>SAT</sup> implies P<sub>btt</sub><sup>SAT</sup> = P<sub><i>m</i>-tt</sub><sup>SAT</sup>
</center>
and for all sets <i>A</i>
<ul>
<li> FP<sub>(<i>m</i>+1)-tt</sub><sup><i>A</i></sup> = FP<sub><i>m</i>-tt</sub><sup><i>A</i></sup> implies FP<sub>btt</sub><sup><i>A</i></sup> = FP<sub><i>m</i>-tt</sub><sup><i>A</i></sup>
</li>
<li> P<sub>(<i>m</i>+1)-T</sub><sup><i>A</i></sup> = P<sub><i>m</i>-T</sub><sup><i>A</i></sup> implies P<sub>bT</sub><sup><i>A</i></sup> = P<sub><i>m</i>-T</sub><sup><i>A</i></sup>
</li>
<li> FP<sub>(<i>m</i>+1)-T</sub><sup><i>A</i></sup> = FP<sub><i>m</i>-T</sub><sup><i>A</i></sup> implies FP<sub>bT</sub><sup><i>A</i></sup> = FP<sub><i>m</i>-T</sub><sup><i>A</i></sup>
</li>
</ul>
where P<sub><i>m</i>-tt</sub><sup><i>A</i></sup> is the set of languages computable by polynomial-time Turing machines that make <i><i>m</i></i> nonadaptive queries to <i>A</i>; P<sub>btt</sub><sup><i>A</i></sup> = <font size=+2>U</font><sub><i>m</i></sub>P<sub><i>m</i>-tt</sub><sup><i>A</i></sup>; P<sub><i>m</i>-T</sub><sup><i>A</i></sup> and P<sub>bT</sub><sup><i>A</i></sup> are the analogous adaptive queries classes; and FP<sub><i>m</i>-tt</sub><sup><i>A</i></sup>, FP<sub>btt</sub><sup><i>A</i></sup>, FP<sub><i>m</i>-T</sub><sup><i>A</i></sup>, and FP<sub>bT</sub><sup><i>A</i></sup> 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
<center>
P<sub>2<i>m</i>-tt</sub><sup><i>A</i></sup> = P<sub><i>m</i>-tt</sub><sup><i>A</i></sup> implies P<sub>btt</sub><sup><i>A</i></sup> = P<sub><i>m</i>-tt</sub><sup><i>A</i></sup>.
</center>
We disprove the conjecture. In fact,
<center>
P<sub>4<i>m</i>/3-tt</sub><sup><i>A</i></sup> = P<sub><i>m</i>-tt</sub><sup><i>A</i></sup> does not imply P<sub>(4<i>m</i>/3+1)-tt</sub><sup><i>A</i></sup> = P<sub>4<i>m</i>/3-tt</sub><sup><i>A</i></sup>.
</center>
Thus there is a P<sub><i>m</i>-tt</sub><sup><i>A</i></sup> hierarchy that contains a finite gap.

We also make progress on the 3-tt vs. 2-tt case:
<center>
P<sub>3-tt</sub><sup><i>A</i></sup> = P<sub>2-tt</sub><sup><i>A</i></sup> implies P<sub>btt</sub><sup><i>A</i></sup> is contained in P<sub>2-tt</sub><sup><i>A</i></sup>/poly.
</center>
</html>



ISSN 1433-8092 | Imprint