The polynomial time hierarchy collapses if the Boolean hierarchy collapses

摘要

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.