The polynomial time hierarchy collapses if the Boolean hierarchy collapses
- 1 January 1988
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 278-292
- https://doi.org/10.1109/sct.1988.5287
Abstract
It is shown that if the Boolean hierarchy (BH) collapses, then there exists a sparse set S such that co-NP contained in NP/sup S/, and therefore the polynomial-time hierarchy (PH) collapses to a subclass of Delta P/3. Since the BH is contained in P/sup NP/, these results relate the internal structure of P/sup 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) are examined.Keywords
This publication has 0 references indexed in Scilit: