Gaps in bounded query hierarchies
Richard Beigel · 2003
Prior results show that most bounded query hierarchies cannot contain finite gaps. For example, it is known that P/sub (m+1)-tt//sup SAT/=P/sub m-tt//sup SAT//spl rArr/P/sub btt//sup SAT/=P/sub m-tt//sup SAT/ and for all sets A/spl middot/FP/sub (m=1)-tt//sup A/=FP/sub m-tt//sup A//spl rArr/FP/sub btt//sup A/=FP/sub m-tt//sup A//spl middot/P/sub (m+1)-T//sup A/=P/sub m-T//sup A/=P/sub bT//sup A//spl middot/FP/sub (m+1)-T//sup A/=FP/sub m-T//sup A//spl rArr/FP/sub bT//sup A/=FP/sub m-T//sup A/ where P/sub m-tt//sup A/ is the set of languages computable by polynomial-time Turing machines that make m nonadaptive queries to A; P/sub btt//sup A/=/spl cup//sub m/P/sub m-tt//sup A/, P/sub m-t//sup A/ and P/sub bT//sup A/ are the analogous adaptive queries classes; and FP/sub m-tt//sup A/, FP/sub btt//sup A/, FP/sub m-T//sup A/, and FP/sub bT//sup 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/sub 2m-tt//sup A/=P/sub m-tt//sup A//spl rArr/P/sub btt//sup A/=P/sub m-tt//sup A/. We disprove the conjecture, in fact, P/sub [4/3m]-tt//sup A/=P/sub m-tt//sup A/not/spl rArr/P/sub ([4/3m]+1)-tt/=P/sub [4/3m]-tt//sup A/. Thus there is a P/sub m-tt//sup A/ hierarchy that contains a finite gap. We also make progress on the 3-tt vs. 2-tt case: P/sub 3-tt//sup A/=P/sub 2-tt//sup A//spl rArr/P/sub btt//sup A//spl sube/P/sub 2-tt//sup A//poly.