7
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ If P=NP then every nontrivial problem in NP is NP-complete. $\endgroup$ – Yuval Filmus Jan 30 at 16:30
22
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.