patternMinor
If $NP \neq co-NP$ then no $NP-complete$ problem can be in $co-NP$
Viewed 0 times
problemcanneqcompletethen
Problem
If $NP \neq co-NP$ then no $NP-complete$ problem can be in $co-NP$.
I found a proof on Wikipedia that I didn't fully get:
https://en.wikipedia.org/wiki/Co-NP
In the line "from this it follows that the set of complements..". Why does it follow? It seems like the author took a complement from both sides of the equation, but that can't be right, can it?
I found a proof on Wikipedia that I didn't fully get:
https://en.wikipedia.org/wiki/Co-NP
In the line "from this it follows that the set of complements..". Why does it follow? It seems like the author took a complement from both sides of the equation, but that can't be right, can it?
Solution
We will show the contrapositive: if some NP-complete problem is in coNP, then NP=coNP. Suppose that $L$ is some NP-complete problem which is in coNP. Let $A$ be any problem in NP. Then there is a polytime reduction $f$ from $A$ to $L$ (since $L$ is NP-complete), which means that $x \in A$ iff $f(x) \in L$. Since $L$ is in coNP, this shows that $A$ is in coNP. Hence NP is a subset of coNP.
Now let $B$ be any problem in coNP. Then there is a polytime reduction $f$ such that $x \in B$ iff $f(x) \in \overline{L}$ (since $L$ is NP-complete and $\overline{B}$ is in NP). Since $\overline{L}$ is in NP, this shows that $B$ is in NP, and so coNP is a subset of NP. We conclude that NP=coNP.
Now let $B$ be any problem in coNP. Then there is a polytime reduction $f$ such that $x \in B$ iff $f(x) \in \overline{L}$ (since $L$ is NP-complete and $\overline{B}$ is in NP). Since $\overline{L}$ is in NP, this shows that $B$ is in NP, and so coNP is a subset of NP. We conclude that NP=coNP.
Context
StackExchange Computer Science Q#76888, answer score: 7
Revisions (0)
No revisions yet.