The Boolean Hierarchy and the Polynomial Hierarchy: A Closer Connection
Richard Chang, Jim Kadin · SIAM Journal on Computing · 1996
We show that if the Boolean hierarchy collapses to level k, then the polynomial hierarchy collapses to ${\text{BH}}_3 (k)$, where ${\text{BH}}_3 (k)$ is the kth level of the Boolean hierarchy over $\Sigma _2^{\text{P}} $. This is an improvement over the known results, which show that the polynomial hierarchy would collapse to ${\text{P}}^{{\text{NP}}^{{\text{NP}}} } [O(\log n)]$. This result is significant in two ways. First, the theorem says that a deeper collapse of the Boolean hierarchy implies a deeper collapse of the polynomial hierarchy. Also, this result points to some previously unexplored connections between the Boolean and query hierarchies of $\Delta _2^{\text{P}} $ and $\Delta _3^{\text{P}} $. Namely,\[ \begin{gathered} {\text{BH}}(k) = {\text{co - BH}}(k) \Rightarrow {\text{BH}}_3 (k) = {\text{co - BH}}_3 (k), \\ {\text{P}}^{{\text{NP}}} \|[k] = {\text{P}}^{{\text{NP}}} \|[k + 1] \Rightarrow {\text{P}}^{{\text{NP}}^{{\text{NP}}} } \|[k + 1] = {\text{P}}^{{\text{NP}}^{{\text{NP}}} } \|[k + 2]. \\ \end{gathered} \]