patternMinor
Does NP=coNP imply P=NP?
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.
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$.
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.