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={𝒫}^{{\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 $𝒫$, 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 $𝒫\subseteq 𝒩𝒫$, it is clear that ${\mathrm{\Delta }}_i^p\subseteq {\mathrm{\Sigma }}_i^p$. Since ${𝒫}^{𝒞}$ is closed under complementation for any complexity class $𝒞$ (the associated machines are deterministic and always halt, so the complementary machine just reverses which states are accepting), if $L\in {𝒫}^{{\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 $𝒫=𝒩𝒫$ then $𝒫=𝒫\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