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

$\endgroup$

migrated from cstheory.stackexchange.com May 21 '13 at 16:52

This question came from our site for theoretical computer scientists and researchers in related fields.

  • 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 May 21 '13 at 17:12
17
$\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}$.

$\endgroup$
  • $\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 May 21 '13 at 17:33
  • 2
    $\begingroup$ the simple proof/ relevant fact is that P is closed under complement! $\endgroup$ – vzn Jan 30 '16 at 16:44

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.