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

If graph isomorphism is in P, is then P = NP?

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

Problem

I think that, since graph isomorphism is not known to be $\textbf{NP}$-complete, we can not reduce all problems in $\textbf{NP}$ to it, and therefore the implication does not hold.

Additionally, in the accepted answer to this question it is stated, that a proof that graph isomorphism is not $\textbf{NP}$-complete would prove $\textbf{P} \neq \textbf{NP}$. Why?

Solution

We don't know.

We do know that $\textbf{P} = \textbf{NP}$ implies graph isomorphism is in $\textbf{P}$, but the other implication has not been proven (to the best of my knowledge). It is suspected graph isomorphism is $\textbf{NP}$-intermediate (i.e., it is in $\textbf{NP} \setminus \textbf{P}$ and not $\textbf{NP}$-complete). This question as well as this other one list evidences supporting said suspicions.

Regarding your second question: If $\textbf{P} = \textbf{NP}$, then any (nontrivial) problem in $\textbf{NP}$ is trivially $\textbf{NP}$-complete because any (nontrivial) problem in $\textbf{P}$ is $\textbf{P}$-complete (and we have assumed $\textbf{P} = \textbf{NP}$). Hence, by contraposition, if the conclusion of this implication is false (i.e., there is a problem in $\textbf{NP}$ which is not $\textbf{NP}$-complete), then the premise (i.e., $\textbf{P} = \textbf{NP}$) must also be false.

Context

StackExchange Computer Science Q#103618, answer score: 22

Revisions (0)

No revisions yet.