THE EXTENDED LOW HIERARCHY IS AN INFINITE HIERARCHY

Balcazar, Book, and Schoning introduced the extended low hierarchy bas ed on the SIGMA-levels of the polynomial-time hierarchy as follows: fo r k greater-than-or-equal-to 1, level k of the extended low hierarchy is the set EL(k)P, SIGMA {A \ SIGMA(k)P(A) subset-or-equal-to SIGMA(k- 1)P (A + SAT)}. Allender and Hemachandra and Long and Sheu introduced refinements of the extended low hierarchy based on the DELTA- and THET A- -levels, respectively, of the polynomial-time hierarchy: for k grea ter-than-or-equal-to 2, EL(k)P, DELTA = {A \ DELTA(k)P (A) subset-or-e qual-to DELTA(k-1)P (A + SAT)} and EL(k)P, THETA = {A \ THETA(k)P (A) subset-or-equal-to THETA(k-1)P (A + SAT)). This paper shows that the e xtended low hierarchy is properly infinite by showing, for k greater-t han-or-equal-to 2, that EL(k)P, SIGMA not-subset-or-equal-to EL(k+1)P, THETA not-subset-or-equal-to EL(k+1)P, DELTA not-subset-or-equal-to E L(k+1)P, SIGMA The proofs use the circuit lower bound techniques of Ha stad and Ko. As corollaries to the constructions, for k greater-than-o r-equal-to 2, oracle sets B(k), C(k), and D(k), such that PH(B(k)) = S IGMA(k)P(B(k)) not-superset-or-equal-to DELTA(k)P (B(k)), PH(C(k)) = D ELTA(k)P (C(k)) not-superset-or-equal-to THETA(k)P (C(k)), and PH(D(k) ) = THETA(k)P(D(k)) not-superset-or-equal-to SIGMA(k-1)P (D(k)) are ob tained.