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

Does NP=coNP imply P=NP?

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

Problem

We know that P=NP implies NP=coNP. Does the reverse implication hold?
Does NP equal coNP imply that P equals NP?
If not why not?

I googled but didn't find the answer.

Solution

The case that $P \subset NP = coNP$ is possible. The reason why $P = NP$ implies $NP = coNP$ is that $P$ is closed under complement, and so if $P = NP$, $NP$ must be closed under complement as well.

A class being closed under complement doesn't necessarily imply anything about its deterministic counterpart. For example, we know that $NL$ is closed under complement, but don't know whether $L = NL$.

Context

StackExchange Computer Science Q#19389, answer score: 6

Revisions (0)

No revisions yet.