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

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

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

Problem

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

Solution

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

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



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

Context

StackExchange Computer Science Q#12195, answer score: 20

Revisions (0)

No revisions yet.