1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ There is a typo in the text you quote. $\Pi^P_2 = \textsf{coNP}$ should read: $\Pi^P_1 = \textsf{coNP}$. $\endgroup$ – quicksort Apr 19 '18 at 0:42
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.