HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Does NP = coNP imply the collapse of PH to level 1?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
conpimplytheleveldoescollapse

Problem

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

Solution

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

Context

StackExchange Computer Science Q#62674, answer score: 6

Revisions (0)

No revisions yet.