8
$\begingroup$

I need to provide one simple evidence that graph isomorphism (GI) is not NP-complete.

I saw a number of papers on google scholar and answers on StackExchange. However, I have very limited knowledge of graph isomorphism, and I would like to just provide one simple evidence which I both understand and can explain clearly.


Below is what I can think of. Is this a valid argument?

Currently, we can solve GI in Quasipolynomial Time. If GI is NP-complete, then we should be able to solve other NP-complete problems in Quasipolynomial Time as well. However, right now, we are unable to solve any NP-complete problem in Quasipolynomial Time. Therefore, GI cannot be in np-complete.

$\endgroup$
3
  • 3
    $\begingroup$ "Nobody knows how" (to solve any NP-complete problem "feasibly") sounds flaky when I think proof. $\endgroup$
    – greybeard
    Nov 15 '20 at 6:21
  • 2
    $\begingroup$ Wikipedia has an explanation which doesn't require Babai's new algorithm: if graph isomorphism is NP-complete, then the polynomial hierarchy collapses. $\endgroup$ Nov 15 '20 at 6:59
  • 1
    $\begingroup$ Your explanation is also good: if graph isomorphism is NP-complete, then ETH is false. $\endgroup$ Nov 15 '20 at 7:00
15
$\begingroup$

The type of argument you are looking for is as follows:

If graph isomorphism were NP-complete, then some widely believed complexity assumption fails.

There are at least two such arguments:

  1. Schöning showed that if graph isomorphism is NP-complete then the polynomial hierarchy collapses to the second level (equivalently, $\Sigma_2^P = \Pi_2^P$).

  2. Babai's quasipolynomial time algorithm implies that if graph isomorphism is NP-complete then the exponential time hypothesis fails.

Whether such arguments are "valid" or not is a sociological question, not a mathematical one.

$\endgroup$
3
  • $\begingroup$ For a non-specialist (me): "the polynomial hierarchy collapses" means P=NP? Then, if understood this correctly, for the OP it seems beneficial to state explicitly that we do not know whether graph isomorphism is NP-complete, but we do know that if graph isomorphism is NP-complete then P=NP, which is thought to be false. We even know that it would imply ETH which in turn is known to imply P=NP, but not the other way around. $\endgroup$
    – Carsten S
    Nov 16 '20 at 10:52
  • $\begingroup$ No, the polynomial hierarchy collapses does not mean that P=NP. In this case it means that $\Sigma_2^P = \Pi_2^P$. $\endgroup$ Nov 16 '20 at 10:54
  • $\begingroup$ Ok, thanks! As I said, I do not know this stuff... $\endgroup$
    – Carsten S
    Nov 16 '20 at 10:55

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.