# polynomial hierarchy is a hierarchy

The polynomial hierarchy is a hierarchy. Specifically:

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

## Proof

To see that $\Sigma^{p}_{i}\cup\Pi^{p}_{i}\subseteq\Delta^{p}_{i+1}=\mathcal{P}^{\Sigma^{p}% _{i}}$, 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 $\Sigma^{p}_{i}$ and $\Pi^{p}_{i}$ respectively.

Since $\mathcal{P}\subseteq\mathcal{NP}$, it is clear that $\Delta^{p}_{i}\subseteq\Sigma^{p}_{i}$. 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}^{\Sigma^{p}_{i}}\subseteq\Sigma^{p}_{i}$ then so is $\overline{L}$, and therefore $L\in\Pi^{p}_{i}$.

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

Title polynomial hierarchy is a hierarchy PolynomialHierarchyIsAHierarchy 2013-03-22 13:02:14 2013-03-22 13:02:14 uzeromay (4983) uzeromay (4983) 5 uzeromay (4983) Result msc 68Q15