The Extended Low Hierarchy is an Infinite Hierarchy
Ming-Jye Sheu, Timothy J. Long · SIAM Journal on Computing · 1994
Balcázar, Book, and Schöning introduced the extended low hierarchy based on the $\Sigma $-levels of the polynomial-time hierarchy as follows: for $k \geqslant 1$, level k of the extended low hierarchy is the set $EL_k^{P,\Sigma } = \{ A|\Sigma _k^P (A) \subseteq \Sigma _{k - 1}^P (A \oplus {\text{SAT}})\} $. Allender and Hemachandra and Long and Sheu introduced refinements of the extended low hierarchy based on the $\Delta $- and $\Theta $-levels, respectively, of the polynomial-time hierarchy: for $k \geqslant 2$, level k, $EL_k^{P,\Delta } = \{ A|\Delta _k^P (A) \subseteq \Delta _{k - 1}^P (A \oplus {\text{SAT}})\} $ and $EL_k^{P,\Theta } = \{ A|\Theta _k^P (A) \subseteq \Theta _{k - 1}^P (A \oplus {\text{SAT}})\} $. This paper shows that the extended low hierarchy is properly infinite by showing, for $k \geqslant 2$, that $EL_k^{P,\Sigma } \subsetneq EL_{k + 1}^{P,\Theta } \subsetneq EL_{k + 1}^{P,\Delta } \subsetneq EL_{k + 1}^{P,\sum } $. The proofs use the circuit lower bound techniques of Håstad and Ko. As corollaries to the constructions, for $k \geqslant 2$, oracle sets $B_k $, $C_k $, and $D_k $, such that ${\operatorname{PH}}(B_k ) = \Sigma _k^P (B_k ) \supsetneq \Delta _k^P (B_k )$, ${\operatorname{PH}}(C_k ) = \Delta _k^P (C_k ) \supsetneq \Theta _k^P (C_k )$, and ${\operatorname{PH}}(D_k ) = \Theta _k^P (D_k ) \supsetneq \sum _{k - 1}^P (D_k )$ are obtained.