# Proving that if coNP $\neq$ NP then P $\neq$ NP

I am new in complexity theory and this question is a part of a homework that I have and I am stuck on it.

Let $${\sf coNP}$$ be the class of languages $$\{\overline{L}: L \in {\sf NP} \}$$.

Show that if $${\sf NP} \neq {\sf coNP}$$, then $${\sf P}\neq {\sf NP}$$.

• What have you tried? We know that $P\subseteq NP$. Also, $P$ is closed under complementation. Can you see how to use these in order to solve the problem? – Shaull May 21 '13 at 17:12

It is maybe easier to consider the contrapositive, that is ${\sf P}={\sf NP} \Rightarrow {\sf NP}={\sf coNP}$.
So assume ${\sf P}={\sf NP}$, then
1. for every $L\in {\sf NP}$, we have $L\in {\sf P}$, and since the languages in ${\sf P}$ are closed under complement, $\bar L\in {\sf P}$ and therefore $L\in {\sf coNP}$.
2. for every $L\in {\sf coNP}$, we have $\bar L\in {\sf P}$, and since the languages in ${\sf P}$ are closed under complement, $L\in {\sf P}$ and therefore $L\in {\sf NP}$.
Remark: Note that if ${\sf P}={\sf NP}$ the polynomial time hierarchy collapses to the lowest level, which implies that ${\sf P}={\sf NP}={\sf coNP}={\sf PH}$.
• the proof that $\Sigma_i^P = \Sigma_{i+1}^P$ implies the PH collapses to the $i$-th level is a very slightly beefed up version of what you wrote. – Sasho Nikolov May 21 '13 at 17:33