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.
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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$.
