# Is there a simple argument why graph isomorphism is not NP-complete?

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.

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

## 1 Answer

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.

• 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. Nov 16 '20 at 10:52
• No, the polynomial hierarchy collapses does not mean that P=NP. In this case it means that $\Sigma_2^P = \Pi_2^P$. Nov 16 '20 at 10:54
• Ok, thanks! As I said, I do not know this stuff... Nov 16 '20 at 10:55