×

The Boolean hierarchy and the polynomial hierarchy: A closer connection. (English) Zbl 0844.68048

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]}. \]

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
PDFBibTeX XMLCite
Full Text: DOI