3
$\begingroup$

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$?

$\endgroup$
4
$\begingroup$

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*}$$

| cite | improve this answer | |
$\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.