×

The polynomial time hierarchy collapses if the Boolean hierarchy collapses. (English) Zbl 0664.03031

Many different complexity hierarchies, e.g. the strong exponential hierarchy, the logarithmic space hierarchy, and the linear space hierarchy, have recently been shown to collapse. This paper presents strong evidence that the Boolean hierarchy (BH), the query hierarchy (QH), and the parallel query hierarchy \((QH_{\|})\) do not collapse. Main results: if the BH, QH, or \(QH_{\|}\) collapses, then the polynomial time hierarchy (PH) collapses to \(P^{NP^{NP}[O(\log n)]}\), a subclass of the third level \(\Delta^ P_ 3\) of the PH. If the PH is an infinite hierarchy as most researchers believe, then the BH, QH, and \(QH_{\|}\) are also infinite hierarchies. Since the BH is contained in \(P^{NP}\), these results relate the internal structure of \(P^{NP}\) to the structure of the PH as a whole. Other conditions that imply the collapse of BH (and the collapse of the PH in turn) include \(D^ P=co- D^ p\), \(P^{NP[k]}=P^{NP[k+1]}\) for any k, and \(P^{NP\| [k]}=P^{NP\| [k+1]}\) for any k.
Reviewer: Tao Renji

MSC:

03D15 Complexity of computation (including implicit computational complexity)
68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite
Full Text: DOI Link