Chang, Richard; Kadin, Jim The Boolean hierarchy and the polynomial hierarchy: A closer connection. (English) Zbl 0844.68048 SIAM J. Comput. 25, No. 2, 340-354 (1996). Summary: 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 \(k\)th level of the Boolean hierarchy over \(\Sigma^{\text{P}}_2\). 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 Bollean 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^{\text{P}}_2\) and \(\Delta^{\text{P}}_3\). Namely, \[ \text{BH}(k)= \text{co-BH}(k)\Rightarrow \text{BH}_2(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]}. \] Cited in 1 ReviewCited in 25 Documents MSC: 68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.) 03D15 Complexity of computation (including implicit computational complexity) 03D20 Recursive functions and relations, subrecursive hierarchies Keywords:Boolean hierarchy; polynomial hierarchy PDFBibTeX XMLCite \textit{R. Chang} and \textit{J. Kadin}, SIAM J. Comput. 25, No. 2, 340--354 (1996; Zbl 0844.68048) Full Text: DOI