principleMajor
Proving that if coNP $\neq$ NP then P $\neq$ NP
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}$.
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
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}$.
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.