The Polynomial Time Hierarchy Collapses If the Boolean Hierarchy Collapses
Jim Kadin · SIAM Journal on Computing · 1988
It is shown that if the Boolean hierarchy (BH) collapses, then there exists a sparse set S such that ${\text{co-NP}} \subseteq {\text{ NP}}^S $, and therefore the polynomial time hierarchy (PH) collapses to ${\text{P}}^{{\text{NP}}^{{\text{NP}}} [O(\log n)]} $, a subclass of $\Delta _3^{\text{P}} $. Since the BH is contained in ${\text{P}}^{{\text{NP}}} $, these results relate the internal structure of ${\text{P}}^{{\text{NP}}} $ to the structure of the PH as a whole. Other conditions that imply the collapse of the BH (and the collapse of the PH in turn include ${\text{D}}^{\text{P}} = {\text{co}}{\text{-}}{\text{D}}^{\text{P}} $, ${\text{P}}^{{\text{NP}}[k]} = {\text{P}}^{{\text{NP}}[k + 1]} $ for any k, and ${\text{P}}^{{\text{NP}}\|[k]} = {\text{P}}^{{\text{NP}}\|[k + 1]} $ for any k. ${\text{P}}^{{\text{NP}}[i]} $ is the class of languages recognizable 1n polynomial time with at most i queries to an oracle from NP, and ${\text{P}}^{{\text{NP}}\|[i]} $ is the class of languages recognizable with at most i parallel queries to an oracle from NP.