<p>Due to Babai's recent result (see the <a href="http://arxiv.org/abs/1512.03547" rel="nofollow noreferrer">paper</a>) $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 
<a href="https://cstheory.stackexchange.com/questions/21571/is-np-in-dtimenpoly-log-n/21660#21660">here</a>. Therefore, if the commonly accepted conjecture $EXP\neq NEXP$ holds, then $GI$ cannot be $NP$-complete.</p>

CC BY-SA 3.0
2015-12-15T17:41:27.197Z
2015-12-15T17:41:27.197Z
2017-04-13T12:32:28.077Z
Andras Farago
<p>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].</p>

<blockquote>
  <p>What other (recent) results can provide further evidence that GI can not be $NP$-complete?</p>
</blockquote>

<p>I posted the question on <a href="https://mathoverflow.net/questions/192014/evidence-that-graph-isomorphism-problem-is-not-np-complete">Mathoverflow</a> without getting an answer.</p>

<p>[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</p>

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

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

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

CC BY-SA 3.0
2015-01-24T18:23:49.617Z
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
CC BY-SA 3.0
2015-01-24T18:40:50.647Z
@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
CC BY-SA 3.0
2015-01-24T19:53:30.650Z
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](http://cstheory.stackexchange.com/questions/8034/what-is-the-current-known-hardness-of-graph-isomorphism)
vzn
CC BY-SA 3.0
2015-01-24T20:13:31.473Z
@lancefortnow Regardless of whether GI is in P or not, proving that GI is not NP-complete implies $P\ne NP$.
Mohammad Al-Turkistany
CC BY-SA 3.0
2015-01-25T01:35:19.527Z
how does that follow? dont see how it follows from implications in the question.
vzn
CC BY-SA 3.0
2015-01-25T06:10:03.117Z
@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
CC BY-SA 3.0
2015-01-25T06:10:21.950Z
@vzn See this post, http://cs.stackexchange.com/questions/7453/if-p-np-why-wouldnt-emptyset-and-sigma-be-np-complete
Mohammad Al-Turkistany
CC BY-SA 3.0
2015-10-24T16:10:40.370Z
@Arul See my comment to VZN. Basically, if P=NP then GI must be NP-complete under Karp reduction.
Mohammad Al-Turkistany
<cc.complexity-theory><graph-isomorphism>
Evidence that Graph Isomorphism problem is not $NP$-complete
Mohammad Al-Turkistany
# Evidence that Graph Isomorphism problem is not $NP$-complete

(Asked by: username_0 on 2015-01-24)

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](https://mathoverflow.net/questions/192014/evidence-that-graph-isomorphism-problem-is-not-np-complete) 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.

**Tags:** cc.complexity-theory, graph-isomorphism
> **Comments:**
> **username_1**: How much more evidence do you need? Let me turn the question around: What evidence is there that GI is not in P?  
> **username_0**: @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?  
> **username_2**: 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](http://cstheory.stackexchange.com/questions/8034/what-is-the-current-known-hardness-of-graph-isomorphism)  
> **username_0**: @lancefortnow Regardless of whether GI is in P or not, proving that GI is not NP-complete implies $P\ne NP$.  
> **username_2**: how does that follow? dont see how it follows from implications in the question.  
> **username_0**: @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).  
> **username_0**: @vzn See this post, http://cs.stackexchange.com/questions/7453/if-p-np-why-wouldnt-emptyset-and-sigma-be-np-complete  
> **username_0**: @Arul See my comment to VZN. Basically, if P=NP then GI must be NP-complete under Karp reduction.  

---

## 1 answers

### Answer by username_3 on 2015-12-15. Score: 11 | Accepted answer

Due to Babai's recent result (see the [paper](http://arxiv.org/abs/1512.03547)) $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](https://cstheory.stackexchange.com/questions/21571/is-np-in-dtimenpoly-log-n/21660#21660). Therefore, if the commonly accepted conjecture $EXP\neq NEXP$ holds, then $GI$ cannot be $NP$-complete.


---

