8
$\begingroup$

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

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ 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? $\endgroup$
    – Shaull
    Commented May 21, 2013 at 17:12

1 Answer 1

Reset to default
20
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Sasho Nikolov
    Commented May 21, 2013 at 17:33
  • 3
    $\begingroup$ the simple proof/ relevant fact is that P is closed under complement! $\endgroup$
    – vzn
    Commented Jan 30, 2016 at 16:44

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.