It was already asked here whether NP=coNP implies P=NP. I'd like to approach that question from the perspective of the Polynomial-Time Hierarchy.

Here is a theorem from Oded Goldreich's "Computational Complexity" (Proposition 3.10):

For every $k \ge 1$, if $\Sigma_k = \Pi_k$ then $\Sigma_k = \Sigma_{k+1}$, which in turn implies $PH = \Sigma_k$.

Now, since $\Sigma_1=NP$ and $\Pi_1 = coNP$, doesn't it imply that $PH = \Sigma_1$, which ultimately implies $P = NP$?


1 Answer 1


No. $PH=NP$ doesn't imply $P=NP$, because $PH$ is not the same class as $P$.

Roughly speaking, $PH$ includes $P$, $NP$, $coNP$, and more: $PH$ includes $\Sigma_i$ and $\Pi_i$ for all $i$. Formally, $PH$ is defined as

$$PH = \Sigma_0 \cup \Pi_0 \cup \Sigma_1 \cup \Pi_1 \cup \Sigma_2 \cup \Pi_2 \cup \cdots.$$

If $NP=coNP$, then we have $\Sigma_1=\Pi_1$, and by Proposition 3.10, we have $\Sigma_1=\Sigma_2=\Sigma_3 =\cdots=NP$ and $\Pi_1=\Pi_2=\Pi_3=\cdots=coNP=NP$, so

$$\begin{align*} PH &= \Sigma_0 \cup \Pi_0 \cup \Sigma_1 \cup \Pi_1 \cup \Sigma_2 \cup \Pi_2 \cup \cdots\\ &= P \cup P \cup NP \cup NP \cup NP \cup NP \cup \cdots\\ &= NP. \end{align*}$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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