# Defining the polynomial hierarchy using $\Pi_i^p$ instead of $\Sigma_i^p$

From Computational Complexity - A Modern Approach, it is claimed in a remark that the following holds true.

Remark 5.5

Note that $$\mathbf\Sigma_1^p = \mathbf{NP}$$ and $$\mathbf\Pi_1^p = \mathbf{coNP}$$. More generally, for every $$i \geq 1$$, $$\mathbf\Pi_i^p = \mathbf{co\Sigma}_i^p = \{ \overline{L} : L \in \mathbf\Sigma_i^p\}$$. Note also that $$\mathbf\Sigma_i^p \subseteq \mathbf\Pi_{i+1}^p$$, and so we can also define the polynomial hierarchy as $$\cup_{i>0} \mathbf\Pi_i^p$$.

However, I am having trouble understanding this. Similar claims are made in lecture notes found on the web, but none of them give a proof since they are all left as exercise. Would it be possible to prove this using NTM instead of verifiers?

• There is a typo in the text you quote. $\Pi^P_2 = \textsf{coNP}$ should read: $\Pi^P_1 = \textsf{coNP}$. Apr 19, 2018 at 0:42

It is a direct consequence of the definition of $\textsf{PH}$.

Remember:

$\qquad \Sigma_i^P = \textsf{NP}^{\Sigma_{i-1}^P}$

$\qquad \Pi_i^P = \textsf{coNP}^{\Sigma_{i-1}^P}$

What we want to prove is:

$\qquad \bigcup_{i>0}\Sigma_i^P = \bigcup_{i>0}\Pi_i^P$

We have:

$\qquad \Sigma^P_i \subseteq \textsf{coNP}^{\Sigma^P_i} = \Pi_{i+1}^P$

$\qquad \Pi^P_i \subseteq \textsf{NP}^{\Pi^P_i} = \textsf{NP}^{\Sigma_i^P} = \Sigma^P_{i+1}$

Taking the union yields:

$\qquad \bigcup_{i>0} \Sigma^P_{i} \subseteq \bigcup_{i>0} \Pi^P_{i} \subseteq \bigcup_{i>0} \Sigma^P_{i}$

which is exactly our goal.