# polynomial hierarchy is a hierarchy

The polynomial hierarchy is a hierarchy. Specifically:

$${\mathrm{\Sigma}}_{i}^{p}\cup {\mathrm{\Pi}}_{i}^{p}\subseteq {\mathrm{\Delta}}_{i+1}^{p}\subseteq {\mathrm{\Sigma}}_{i+1}^{p}\cap {\mathrm{\Pi}}_{i+1}^{p}.$$ |

## Proof

To see that ${\mathrm{\Sigma}}_{i}^{p}\cup {\mathrm{\Pi}}_{i}^{p}\subseteq {\mathrm{\Delta}}_{i+1}^{p}={\mathcal{P}}^{{\mathrm{\Sigma}}_{i}^{p}}$, observe that the machine which checks its input against its oracle and accepts or rejects when the oracle accepts or rejects (respectively) is easily in $\mathcal{P}$, as is the machine which rejects or accepts when the oracle accepts or rejects (respectively). These easily emulate ${\mathrm{\Sigma}}_{i}^{p}$ and ${\mathrm{\Pi}}_{i}^{p}$ respectively.

Since $\mathcal{P}\subseteq \mathcal{N}\mathcal{P}$, it is clear that
${\mathrm{\Delta}}_{i}^{p}\subseteq {\mathrm{\Sigma}}_{i}^{p}$. Since ${\mathcal{P}}^{\mathcal{C}}$ is
closed
under complementation for any
complexity class^{}
$\mathcal{C}$ (the associated
machines are deterministic^{} and always halt, so the complementary machine just
reverses which states are accepting), if
$L\in {\mathcal{P}}^{{\mathrm{\Sigma}}_{i}^{p}}\subseteq {\mathrm{\Sigma}}_{i}^{p}$ then so is $\overline{L}$,
and therefore $L\in {\mathrm{\Pi}}_{i}^{p}$.

Unlike the arithmetical hierarchy, the polynomial hierarchy is not known to be proper. Indeed, if $\mathcal{P}=\mathcal{N}\mathcal{P}$ then $\mathcal{P}=\mathcal{P}\mathscr{H}$, so a proof that the hierarchy is proper would be quite significant.

Title | polynomial hierarchy is a hierarchy |
---|---|

Canonical name | PolynomialHierarchyIsAHierarchy |

Date of creation | 2013-03-22 13:02:14 |

Last modified on | 2013-03-22 13:02:14 |

Owner | uzeromay (4983) |

Last modified by | uzeromay (4983) |

Numerical id | 5 |

Author | uzeromay (4983) |

Entry type | Result |

Classification | msc 68Q15 |