2
$\begingroup$

A simple fact is that $P = NP \to P = coNP$, which follows from the observation that $P$ is closed under complement.

I am having trouble seeing that an analogous statement is true at higher levels of $PH$. For example, is it known that $NP = \Sigma_2 P$ implies $NP = \Pi_2 P$? If so, is there an easy proof? Would such a statement have any other interesting implications (For example $NP = coNP$)?

It seems somewhat likely to me that this is true, based on the observation that $NP = \Sigma_2 P$ means that $\exists \forall$ quantifier patterns can be replaced with $\exists$ quantifier patterns, and so all higher levels of $PH$ would at least collapse to $\Pi_2 P$.

$\endgroup$
4
$\begingroup$

The answer is yes. notice that $NP=\Sigma_1$ and for all $i$ you have $\Sigma_i=\Sigma_{i+1} \Rightarrow \Sigma_i=\Pi_i$. This is true since $\Pi_i\subseteq \Sigma_{i+1}=\Sigma_i$. The inclusion holds since if $\bar{L}\in\Sigma_i$ then you have $x\notin L \iff \exists v_1\in \left\{0,1\right\}^{p(|v_1|)}...Q_iv_i\in\left\{0,1\right\}^{p(|v_i|)}M(x,v_1,...,v_i)=1 $ or equivalently $x\in L \iff \forall v_1\in \left\{0,1\right\}^{p(|v_1|)}...\bar{Q_i}v_i\in\left\{0,1\right\}^{p(|v_i|)}M(x,v_1,...,v_i)=0$. So now your $\Sigma_{i+1}$ verifier for $L$ will ignore $v_1$, run $M(v_2,...,v_{i+1})$ and flip the answer. It remains to show $\Sigma_i\subseteq\Pi_i$. Let $L\in\Sigma_i, \bar{L}\in \Sigma_{i+1}$ and since $\Sigma_i=\Sigma_{i+1}$ you get $\bar{L}\in\Sigma_i$.

Back to your question. If $NP=\Sigma_2$ (or $\Sigma_1=\Sigma_2)$ then $\Sigma_1=\Pi_1$. Let $L\in\Pi_2$ then $\bar{L}\in\Sigma_2\Rightarrow \bar{L}\in\Sigma_1\Rightarrow \bar{L}\in\Pi_1\Rightarrow L\in\Sigma_1$, So $L\in NP$ as required. The opposite direction is clear(for all $i$ $\Sigma_i\subseteq\Pi_{i+1}$).

$\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.