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

If $NP \neq co-NP$ then no $NP-complete$ problem can be in $co-NP$

Submitted by: @import:stackexchange-cs··
0
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?

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.

Context

StackExchange Computer Science Q#76888, answer score: 7

Revisions (0)

No revisions yet.