principleModerate
If NP $\neq$ Co-NP then is P $\neq$ NP
Viewed 0 times
neqthenstackoverflow
Problem
Does the proof of the widely believed result P $\neq$ NP depend on the proof of NP $\neq$ Co-NP ?
Solution
Only in one direction. As $\mathsf{P}=\text{co-}\mathsf{P}$, if $\mathsf{NP}\neq\text{co-}\mathsf{NP}$ then we would know that $\mathsf{P}\neq\mathsf{NP}$. However the reverse implication doesn't hold. If $\mathsf{P}\neq\mathsf{NP}$ then it's possible that either $\mathsf{NP}\neq\text{co-}\mathsf{NP}$ or $\mathsf{NP}=\text{co-}\mathsf{NP}$.
Context
StackExchange Computer Science Q#7861, answer score: 10
Revisions (0)
No revisions yet.