Evidence that Graph Isomorphism problem is not $NP$-complete

Question

Graph isomorphism problem is one of the longest standing problems that resisted classification into $P$ or $NP$-complete problems. We have evidences that it can not be $NP$-complete. Firstly, Graph Isomorphism can not be $NP$-complete unless the polynomial hierarchy [1] collapses to the second level. Also, the counting[2] version of GI is polynomial-time Turing equivalent to its decision version which does not hold for any known $NP$-complete problem. The counting version of $NP$-complete problems seems to have much higher complexity. Finally, the lowness result [3] of GI with respect to $PP$ ($PP^{GI}=PP$) is not known to hold for any $NP$-complete problem. The lowness result of GI has been improved to $SPP^{GI}=SPP$ after Arvind and Kurur proved that GI is in $SPP$ [4].

What other (recent) results can provide further evidence that GI can not be $NP$-complete?

I posted the question on Mathoverflow without getting an answer.

[1]: Uwe Schöning, "Graph isomorphism is in the low hierarchy", Proceedings of the 4th Annual Symposium on Theoretical Aspects of Computer Science, 1987, 114–124

[2]: R. Mathon, "A note on the graph isomorphism counting problem", Information Processing Letters, 8 (1979) pp. 131–132

[3]: Köbler, Johannes; Schöning, Uwe; Torán, Jacobo (1992), "Graph isomorphism is low for PP", Computational Complexity 2 (4): 301–330

[4]: V. Arvind and P. Kurur. Graph isomorphism is in SPP, ECCC TR02-037, 2002.

How much more evidence do you need? Let me turn the question around: What evidence is there that GI is not in P? — Lance Fortnow, Jan 24 '15 at 18:23
@LanceFortnow I think the fact that we do not have even a quasi-polynomial time algorithm for GI is the best evidence that GI is not in $P$. Are you aware of others? — Mohammad Al-Turkistany, Jan 24 '15 at 18:40
circumstantial evidence that GI is in P is that (afaik/afact) nobody can construct non-P hard instances (even at random?) & there dont even seem to be any (conjectured) candidates. ps this question seems close to what is the current known hardness of GI — vzn, Jan 24 '15 at 19:53
@lancefortnow Regardless of whether GI is in P or not, proving that GI is not NP-complete implies $P\ne NP$. — Mohammad Al-Turkistany, Jan 24 '15 at 20:13
how does that follow? dont see how it follows from implications in the question. — vzn, Jan 25 '15 at 01:35
@vzn It is HW problem to prove that if ${\sf P}={\sf NP}$, all languages in ${\sf P}$ except for $\emptyset$ and $\Sigma^*$ would be ${\sf NP}$-complete ( this is under Karp reductions). — Mohammad Al-Turkistany, Jan 25 '15 at 06:10
@vzn See this post, http://cs.stackexchange.com/questions/7453/if-p-np-why-wouldnt-emptyset-and-sigma-be-np-complete — Mohammad Al-Turkistany, Jan 25 '15 at 06:10
@MohammadAl-Turkistany why "proving that GI is not NP-complete implies P≠NP"? — , Oct 24 '15 at 09:40
@Arul See my comment to VZN. Basically, if P=NP then GI must be NP-complete under Karp reduction. — Mohammad Al-Turkistany, Oct 24 '15 at 16:10

score 11 · Accepted Answer · edited Apr 13 '17 at 12:32

11

Due to Babai's recent result (see the paper) $GI$ is in quasi-polynomial time ($QP$). If $GI$ is $NP$-complete, then it implies $NP\subseteq QP=DTIME(n^{polylog\, n})$. This, in turn, implies $EXP=NEXP$, see here. Therefore, if the commonly accepted conjecture $EXP\neq NEXP$ holds, then $GI$ cannot be $NP$-complete.

edited Apr 13 '17 at 12:32

Community

1

answered Dec 15 '15 at 17:41

Andras Farago

11,396
37
70

Evidence that Graph Isomorphism problem is not $NP$-complete

1 Answers1

Linked