The Polynomial Time Hierarchy Collapses If the Boolean Hierarchy Collapses
- 1 December 1988
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 17 (6) , 1263-1282
- https://doi.org/10.1137/0217080
Abstract
The structure of the Boolean hierarchy (BH) is related to the polynomial time hierarchy (PH) by showing that if the BH collapses, then $PH \subseteq \Delta^{P}_{3}$.
This publication has 14 references indexed in Scilit:
- PNP[(log )] and sparse turing-complete sets for NPJournal of Computer and System Sciences, 1989
- The Boolean Hierarchy I: Structural PropertiesSIAM Journal on Computing, 1988
- Graph Minimal Uncolorability is ${\text{D}}^{\text{p}} $-CompleteSIAM Journal on Computing, 1987
- The logarithmic alternation hierarchy collapses: $$A\Sigma _2^\mathcal{L} = A\Pi _2^\mathcal{L}$$Published by Springer Nature ,1987
- Parity, circuits, and the polynomial-time hierarchyTheory of Computing Systems, 1984
- The complexity of facets (and some facets of complexity)Journal of Computer and System Sciences, 1984
- Sparse complete sets for NP: Solution of a conjecture of Berman and HartmanisJournal of Computer and System Sciences, 1982
- A note on sparse oracles for NPJournal of Computer and System Sciences, 1982
- On Isomorphisms and Density of $NP$ and Other Complete SetsSIAM Journal on Computing, 1977
- A comparison of polynomial time reducibilitiesTheoretical Computer Science, 1975