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

If NP $\neq$ Co-NP then is P $\neq$ NP

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