<p>The smallest set of permutations you have to check to verify that no non-trivial permutations exist in a black box setting is better than $n!$ but still exponential, <a href="http://oeis.org/A186202" rel="nofollow">OEIS A186202</a>. </p>

<p>The number of bits needed to store an unlabeled graph is $log_{2}$ of ${n\choose 2}-n log(n) +O(n)$. See Naor, Moni. "Succinct representation of general unlabeled graphs." Discrete Applied Mathematics 28.3 (1990): 303-307. The compression method proof is a bit cleaner if I recall. Anyway, lets call that set $U$. Let $L=2^{{n\choose 2}}$ for labeled graphs.</p>

<pre><code>--Haskell notation
graphCanonicalForm :: L -&gt; U

graphIsomorphism :: L -&gt; L -&gt; Bool
graphIsomorphism a b = (graphCanonicalForm a) == (graphCanonicalForm b)    
</code></pre>

<p>$U^L$ and $Bool^{L^{L}}$ if you convert to exponentials. Just examining their type signatures putting graphs in canonical form looks easier, but as shown above GC makes GI easy.</p>

CC BY-SA 3.0
2015-08-03T08:50:47.373Z
Thanks. How strong is this kind of arguments?
Mohammad Al-Turkistany
CC BY-SA 3.0
2015-08-04T03:01:09.450Z
is there a ref to be cited that documents this connection further?
vzn
CC BY-SA 3.0
2015-08-05T02:33:19.060Z
@MohammadAl-Turkistany: This is basically a query complexity argument. But known algorithms, e.g. Babai-Luks 1983, already beat this bound, I think by quite a significant margin (something like $2^n$ versus $2^{\sqrt{n}}$).
Joshua Grochow
CC BY-SA 3.0
2015-08-05T02:48:35.957Z
Has anyone ever coded up Babai-Luks? I've always wanted to benchmark it's average case complexity.
Chad Brewbaker
CC BY-SA 3.0
2015-08-05T04:58:04.780Z
@ChadBrewbaker: If your concern is being coded up, and average-case complexity I'm sure that nauty does significantly better than your algorithm. (Note that the best known lower bound on nauty is $\Omega(2^{n/20})$ (Miyazaki 1996), and a poly-time algorithm was found for the Miyazaki graphs. A simple analysis shows a lower bound of $(3/2)^n$ on your algorithm.) Also, GI is in average-case *linear* time (Babai-Kucera).
Joshua Grochow
CC BY-SA 3.0
2015-08-05T12:58:21.147Z
@JoshuaGrochow Thanks for your insightful comments. What is your personal opinion? Do you have any reason to believe that GI is not in P? BTW, I find it terribly amazing that we don't know why there is no known PTIME Turing reduction from GI to GA.
Mohammad Al-Turkistany
CC BY-SA 3.0
2015-08-05T17:11:26.487Z
@JoshuaGrochow I was wondering if anyone had coded Babai-Luks. Yes, NAUTY in practice is faster than black-box, but NAUTY could benefit from only querying each primal permutation group at most once.
Chad Brewbaker
CC BY-SA 3.0
2015-08-05T21:18:11.097Z
@ChadBrewbaker: Sorry, I may have been reading too far between the lines of your question. As far as I know, Babai-Luks has not been coded up. Does nauty even have routines for *just* testing GA, rather than for computing generators of Aut(G) (the latter being equivalent to GI)? I think it just so completely avoids the black-box permutation-querying approach that I'm not sure if nauty would benefit as you suggest.
Joshua Grochow
CC BY-SA 3.0
2015-08-05T22:48:04.460Z
@MohammadAl-Turkistany: this question has made me think more deeply about my beliefs on the complexity of GI. Re: your other question, note that if there is no poly-time Turing (or even many-one) reduction from GI to GA then P$\neq$NP.
Joshua Grochow
CC BY-SA 3.0
2015-08-09T16:23:44.433Z
@JoshuaGrochow correct, NAUTY does a DFS to put each graph in a canonical permutation; saving automorphisms as it goes. CAGES does a great job explaining it, http://www.math.mtu.edu/~kreher/cages.html
Chad Brewbaker
CC BY-SA 3.0
2015-08-02T16:28:19.613Z
2015-08-05T02:25:14.880Z
2015-08-05T02:25:14.880Z
Chad Brewbaker
<p>Kozen in his paper, <a href="http://dl.acm.org/citation.cfm?id=990529" rel="nofollow">A clique problem equivalent to graph isomorphism</a>, gives an evidence that $GI$ is not in $P$. The following is from the paper:</p>

<blockquote>
  <p>"Nevertheless, it is likely that finding a polynomial time algorithm for graph isomorphism will be as difficult as finding a polynomial time algorithm for an NP-complete problem. In support of this claim, we give a problem equivalent to graph isomorphism, a small perturbation of which is NP-complete."</p>
</blockquote>

<p>Also, Babai in his recent breakthrough paper <a href="http://arxiv.org/abs/1512.03547" rel="nofollow">Graph Isomorphism in quasipolynomial time</a> gives an argument against the existence of efficient algorithms for GI. He observes that the group isomorphism problem (which is reducible to GI) is a major obstacle to placing GI in $P$. Group Isomorphism problem ( groups are given by their Cayley tableis) is solvable in $n^{O(\log n)}$ and it is not known to be in $P$. </p>

<p>Here is an excerpt from Babai's paper:</p>

<blockquote>
  <p>The result of the present paper amplifies the significance of the Group Isomorphism problem (and the challenge problem stated) as a barrier to placing GI in P. It is quite possible that the intermediate status of GI (neither NP-complete, nor polynomial time) will persist.</p>
</blockquote>

CC BY-SA 3.0
2015-08-05T05:25:32.940Z
From Kozen's Lem. 3 one can get a simpler example of this phenomenon: namely, Induced Subgraph Isomorphism (is $H$ an induced subgraph of $G$) is exactly GI when $|G|=|H|$, but is NP-hard when $|G|=c|H|$ for any $c > 1$. For discrete parameters, we know there are problems in P that quickly become NP-complete (e.g. 2SAT vs 3SAT). Do you know if there are examples of problems in P with some continuous parameter that become NP-complete at a sharp threshold? If so, then this kind of reasoning wouldn't be much evidence that GI isn't in P, but I can't think of such an example off the top of my head.
Joshua Grochow
CC BY-SA 3.0
2015-08-05T13:29:19.943Z
@JoshuaGrochow No, I am not aware of any such decision problems. But for optimization problems I know that finding an assignment satisfying $7/8$ of the clauses is in $P$ while finding an assignment satisfying $7/8+ϵ$  of the clauses is $NP$-hard even for satisfiable 3SAT formulas ($ϵ>0$ ).
Mohammad Al-Turkistany
CC BY-SA 3.0
2015-12-20T18:29:33.147Z
Oops, Klimpel's answer already contains the group isomorphism evidence. Anyway, it is useful to have Babai's perspective on the matter.
Mohammad Al-Turkistany
CC BY-SA 3.0
2017-01-04T21:55:17.323Z
[Babai retracted the claim of quasipolynomial runtime](http://people.cs.uchicago.edu/~laci/update.html). Apparently there was an error in the analysis.
Raphael
CC BY-SA 3.0
2015-08-03T20:14:35.523Z
2015-12-20T18:18:56.447Z
2015-12-20T18:18:56.447Z
Mohammad Al-Turkistany
<p>here are other results not cited yet</p>

<ul>
<li><p><a href="http://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.190/Mitarbeiter/toran/hard.pdf">On the hardness of Graph Isomorphism</a> / Torán
FOCS 2000 and SIAM J. Comput. 33, 5 1093-1108.</p>

<blockquote>
  <p>We show that the graph isomorphism problem is hard under DLOGTIME uniform AC<sup>0</sup> many-one reductions for the complexity classes NL, PL (probabilistic logarithmic space) for every logarithmic space modular class Mod<sub>k</sub>L and for the class DET of problems NC<sup>1</sup> reducible to the determinant. These are the strongest known hardness results for the graph isomorphism problem and imply a randomized logarithmic space reduction from the perfect matching problem to graph isomorphism. We also investigate hardness results for the graph automorphism problem.</p>
</blockquote></li>
<li><p><a href="http://eccc.hpi-web.de/report/2010/117/download/">Graph Isomorphism is not AC<sup>0</sup> reducible to Group Isomorphism</a> / Chattopadhyay, Toran, Wagner</p>

<blockquote>
  <p>We give a new upper bound for the Group and Quasigroup Isomorphism problems when the input structures are given explicitly by multiplication tables. We show that these problems can be computed by polynomial size nondeterministic circuits of unbounded fan-in with O(log log n) depth and O(log<sup>2</sup> n) nondeterministic bits, where n is the number of group elements. This improves the existing upper bound from [Wol94] for the problems. In the previous upper bound the circuits have bounded fanin but depth O(log<sup>2</sup> n) and also O(log<sup>2</sup> n) nondeterministic bits. We then prove that the kind of circuits from our upper bound cannot compute the Parity function. Since Parity is AC<sup>0</sup> reducible to Graph Isomorphism, this implies that Graph Isomorphism is strictly harder than Group or Quasigroup Isomorphism under the ordering defined by AC<sup>0</sup> reductions.</p>
</blockquote></li>
</ul>

CC BY-SA 3.0
2015-08-05T05:07:21.443Z
Although these are indeed the strongest known lower bounds on GI, they don't really say anything about its not being in P. In the first case, DET isn't so close to P. In the second case, note that the structure of the $\mathsf{AC}^0$-degrees within P is already quite rich.
Joshua Grochow
CC BY-SA 3.0
2015-08-05T14:55:45.267Z
re "strongest known lower bounds on GI", ofc GI is in NP so an actual proof that GI is not in P is equivalent to P≠NP! (possibly via [NPI](https://en.wikipedia.org/wiki/NP-intermediate)≠∅)...
vzn
CC BY-SA 3.0
2015-08-05T21:13:00.507Z
Yes, but, for example, it would be nice to know that GI is P-hard! (Of course, P-hardness has very little to do with showing that something is not in P, but it would at least suggest that GI is not in NC!)
Joshua Grochow
CC BY-SA 3.0
2015-08-04T03:25:26.317Z
2015-08-04T03:25:26.317Z
vzn
<p>Before this question, my opinion was that Graph Isomorphism might be in P, i.e. that there is no evidence to believe that GI is not in P. So I asked myself what would count as evidence for me: If there were mature algorithms for $p$-group isomorphism that fully exploited the available structure of $p$-groups and still would have no hope to achieve polynomial runtime, then I would agree that GI is probably not in P. There are known algorithms that exploit the available structure like <a href="http://www.ams.org/mathscinet-getitem?mr=1283739"><em>Isomorphism testing for $p$-groups.</em> by O'Brien (1994)</a>, but I haven't read it in sufficient detail to judge whether it fully exploits the available structure, or whether there is any hope to improve this algorithm (without exploiting additional non-obvious structure of $p$-groups) to achieve polynomial runtime.</p>

<p>But I knew that Dick Lipton called for action near the end of 2011 to clarify the computational complexity of the group isomorphism problem in general, and of the $p$-group isomorphism problem specifically. So I googled for</p>

<pre><code>site:https://rjlipton.wordpress.com group isomorphism
</code></pre>

<p>in order to see whether the call for action had been successful. It was indeed:</p>

<ol>
<li><a href="https://rjlipton.wordpress.com/2011/11/07/the-group-isomorphism-problem-a-possible-polymath-problem/">The Group Isomorphism Problem: A Possible Polymath Problem?</a></li>
<li><a href="https://rjlipton.wordpress.com/2013/05/11/advances-on-group-isomorphism/">Advances on Group Isomorphism</a></li>
<li><a href="https://rjlipton.wordpress.com/2014/02/17/three-from-ccc/">Three From CCC: Progress on Group Isomorphism</a></li>
</ol>

<p>The last post reviews a paper which achieves $n^{O(\log \log n)}$ runtime for certain important families of groups, exploits much of the available structure, and acknowledges the above mentioned paper from 1994. Because the $n^{O(\log \log n)}$ runtime bound is both compatible with the experience that graph isomorphism is not hard in practice, and with the experience that nobody is able to come up with a polynomial time algorithm (even for group isomorphism), this can be counted as evidence that GI is not in P.</p>

CC BY-SA 3.0
2015-08-03T08:54:40.047Z
https://rjlipton.wordpress.com/2015/03/05/news-on-intermediate-problems/ also turned up by my search. It cites **Theorem 2** *Graph Isomorphism is in ${\mathsf{RP}^{\mathrm{MCSP}}}$. Moreover, every promise problem in ${\mathsf{SZK}}$ belongs to ${\mathsf{BPP}^{\mathrm{MCSP}}}$ as defined for promise problems.* This is evidence that GI is not NP-complete, but this wasn't the question here. Let me add that I see no problem with the length or style of my answer, because I interpret a request for evidence as a request for a reasoned opinion.
Thomas Klimpel
CC BY-SA 3.0
2015-08-04T04:47:42.340Z
I don't follow your reasoning. How can you know that the "available structure" is "fully exploited"? If anything, doesn't the Grochow-Qiao paper suggest that much more can be done with cohomology classes?
Sasho Nikolov
CC BY-SA 3.0
2015-08-04T07:58:06.030Z
@SashoNikolov By the "available structure", I mean the knowledge about the structure in the group theory community, related communities and existing publications. Examples were the structure is not "fully exploited" are publications whose main goal is to come up with a practical implementable algorithm, which therefore stop at some point and just mention the remaining limitations without clear indications whether those are fundamental. The Grochow-Qiao paper reviewed those and directly attacked the computational complexity of group isomorphism, hence its results provide good evidence.
Thomas Klimpel
CC BY-SA 4.0
2020-08-24T16:31:17.970Z
@ThomasKlimpel I have a simple clarification. If $P=NP$ then is $\#GI$ is $\#P$-complete?
Turbo
CC BY-SA 3.0
2015-08-03T08:37:55.167Z
2015-08-03T08:37:55.167Z
Thomas Klimpel
<p>Motivated by Fortnow's comment on my post, <a href="https://cstheory.stackexchange.com/questions/29266/evidence-that-graph-isomorphism-problem-is-not-np-complete">Evidence that Graph Isomorphism problem is not $NP$-complete</a>, and by the fact that $GI$ is a prime candidate for $NP$-intermediate problem (not $NP$-complete nor in $P$), I am interested in known evidences that $GI$ is not in $P$.</p>

<p>One such evidence is the $NP$-completeness of a restricted Graph Automorphism problem(fixed-point free graph automorphism problem is $NP$-complete). This problem and other generalizations of $GI$ were studied in "<a href="http://epubs.siam.org/doi/abs/10.1137/0210002" rel="noreferrer">Some NP-complete problems similar to Graph Isomorphism</a>" by Lubiw. Some may argue as evidence the fact that despite more than 45 years no one found polynomial-time algorithm for $GI$. </p>

<blockquote>
  <p>What other evidence do we have to believe that $GI$ is not in $P$?</p>
</blockquote>

CC BY-SA 3.0
2015-08-02T22:51:05.903Z
Somewhat weak evidence is the growing class of problems that are logspace-equivalent to GI, yet none of which seems to have obvious polytime algorithms.  (Of course, if one of them does have a polytime algorithm then they all do.)
András Salamon
CC BY-SA 3.0
2015-08-03T20:29:19.950Z
circumstantial evidence similar to P vs NP: decades of optimization of GI algorithms eg [nauty](http://www3.cs.stonybrook.edu/~algorith/implement/nauty/implement.shtml) that still have experimentally verifiable non-P worst case trends, apparently mainly on random regular graphs.
vzn
CC BY-SA 3.0
2015-08-04T03:02:57.230Z
see also [hard graphs for GI testing](http://cstheory.stackexchange.com/questions/5956/hard-instances-for-graph-isomorphism-testing)
vzn
CC BY-SA 4.0
2019-11-22T10:53:39.397Z
What do you think about this? http://www.dharwadker.org/tevet/isomorphism/
Anna Tomskova
CC BY-SA 4.0
2020-11-19T00:32:40.937Z
wrong, see https://cstheory.stackexchange.com/a/32291
mdeff
<cc.complexity-theory><graph-isomorphism>
What evidence is there that Graph Isomorphism is not in $P$?
Mohammad Al-Turkistany
# What evidence is there that Graph Isomorphism is not in $P$?

(Asked by: username_0 on 2015-08-02)

Motivated by Fortnow's comment on my post, [Evidence that Graph Isomorphism problem is not $NP$-complete](https://cstheory.stackexchange.com/questions/29266/evidence-that-graph-isomorphism-problem-is-not-np-complete), and by the fact that $GI$ is a prime candidate for $NP$-intermediate problem (not $NP$-complete nor in $P$), I am interested in known evidences that $GI$ is not in $P$.

One such evidence is the $NP$-completeness of a restricted Graph Automorphism problem(fixed-point free graph automorphism problem is $NP$-complete). This problem and other generalizations of $GI$ were studied in "[Some NP-complete problems similar to Graph Isomorphism](http://epubs.siam.org/doi/abs/10.1137/0210002)" by Lubiw. Some may argue as evidence the fact that despite more than 45 years no one found polynomial-time algorithm for $GI$.

> What other evidence do we have to believe that $GI$ is not in $P$?

**Tags:** cc.complexity-theory, graph-isomorphism
> **Comments:**
> **username_1**: Somewhat weak evidence is the growing class of problems that are logspace-equivalent to GI, yet none of which seems to have obvious polytime algorithms.  (Of course, if one of them does have a polytime algorithm then they all do.)  
> **username_2**: circumstantial evidence similar to P vs NP: decades of optimization of GI algorithms eg [nauty](http://www3.cs.stonybrook.edu/~algorith/implement/nauty/implement.shtml) that still have experimentally verifiable non-P worst case trends, apparently mainly on random regular graphs.  
> **username_2**: see also [hard graphs for GI testing](http://cstheory.stackexchange.com/questions/5956/hard-instances-for-graph-isomorphism-testing)  
> **username_3**: What do you think about this? http://www.dharwadker.org/tevet/isomorphism/  
> **username_4**: wrong, see https://cstheory.stackexchange.com/a/32291  

---

## 4 answers

### Answer by username_8 on 2015-08-03. Score: 16 | Accepted answer

Before this question, my opinion was that Graph Isomorphism might be in P, i.e. that there is no evidence to believe that GI is not in P. So I asked myself what would count as evidence for me: If there were mature algorithms for $p$-group isomorphism that fully exploited the available structure of $p$-groups and still would have no hope to achieve polynomial runtime, then I would agree that GI is probably not in P. There are known algorithms that exploit the available structure like Isomorphism testing for $p$-groups. by O'Brien (1994), but I haven't read it in sufficient detail to judge whether it fully exploits the available structure, or whether there is any hope to improve this algorithm (without exploiting additional non-obvious structure of $p$-groups) to achieve polynomial runtime.
But I knew that Dick Lipton called for action near the end of 2011 to clarify the computational complexity of the group isomorphism problem in general, and of the $p$-group isomorphism problem specifically. So I googled for
site:https://rjlipton.wordpress.com group isomorphism

in order to see whether the call for action had been successful. It was indeed:

The Group Isomorphism Problem: A Possible Polymath Problem?
Advances on Group Isomorphism
Three From CCC: Progress on Group Isomorphism

The last post reviews a paper which achieves $n^{O(\log \log n)}$ runtime for certain important families of groups, exploits much of the available structure, and acknowledges the above mentioned paper from 1994. Because the $n^{O(\log \log n)}$ runtime bound is both compatible with the experience that graph isomorphism is not hard in practice, and with the experience that nobody is able to come up with a polynomial time algorithm (even for group isomorphism), this can be counted as evidence that GI is not in P.

> **Comments:**
> **username_8**: https://rjlipton.wordpress.com/2015/03/05/news-on-intermediate-problems/ also turned up by my search. It cites **Theorem 2** *Graph Isomorphism is in ${\mathsf{RP}^{\mathrm{MCSP}}}$. Moreover, every promise problem in ${\mathsf{SZK}}$ belongs to ${\mathsf{BPP}^{\mathrm{MCSP}}}$ as defined for promise problems.* This is evidence that GI is not NP-complete, but this wasn't the question here. Let me add that I see no problem with the length or style of my answer, because I interpret a request for evidence as a request for a reasoned opinion.  
> **username_9**: I don't follow your reasoning. How can you know that the "available structure" is "fully exploited"? If anything, doesn't the Grochow-Qiao paper suggest that much more can be done with cohomology classes?  
> **username_8**: @SashoNikolov By the "available structure", I mean the knowledge about the structure in the group theory community, related communities and existing publications. Examples were the structure is not "fully exploited" are publications whose main goal is to come up with a practical implementable algorithm, which therefore stop at some point and just mention the remaining limitations without clear indications whether those are fundamental. The Grochow-Qiao paper reviewed those and directly attacked the computational complexity of group isomorphism, hence its results provide good evidence.  
> **username_10**: @ThomasKlimpel I have a simple clarification. If $P=NP$ then is $\#GI$ is $\#P$-complete?  

---

### Answer by username_5 on 2015-08-02. Score: 12

The smallest set of permutations you have to check to verify that no non-trivial permutations exist in a black box setting is better than $n!$ but still exponential, OEIS A186202. 
The number of bits needed to store an unlabeled graph is $log_{2}$ of ${n\choose 2}-n log(n) +O(n)$. See Naor, Moni. "Succinct representation of general unlabeled graphs." Discrete Applied Mathematics 28.3 (1990): 303-307. The compression method proof is a bit cleaner if I recall. Anyway, lets call that set $U$. Let $L=2^{{n\choose 2}}$ for labeled graphs.
--Haskell notation
graphCanonicalForm :: L -> U

graphIsomorphism :: L -> L -> Bool
graphIsomorphism a b = (graphCanonicalForm a) == (graphCanonicalForm b)    

$U^L$ and $Bool^{L^{L}}$ if you convert to exponentials. Just examining their type signatures putting graphs in canonical form looks easier, but as shown above GC makes GI easy.

> **Comments:**
> **username_0**: Thanks. How strong is this kind of arguments?  
> **username_2**: is there a ref to be cited that documents this connection further?  
> **username_6**: @MohammadAl-Turkistany: This is basically a query complexity argument. But known algorithms, e.g. Babai-Luks 1983, already beat this bound, I think by quite a significant margin (something like $2^n$ versus $2^{\sqrt{n}}$).  
> **username_5**: Has anyone ever coded up Babai-Luks? I've always wanted to benchmark it's average case complexity.  
> **username_6**: @ChadBrewbaker: If your concern is being coded up, and average-case complexity I'm sure that nauty does significantly better than your algorithm. (Note that the best known lower bound on nauty is $\Omega(2^{n/20})$ (Miyazaki 1996), and a poly-time algorithm was found for the Miyazaki graphs. A simple analysis shows a lower bound of $(3/2)^n$ on your algorithm.) Also, GI is in average-case *linear* time (Babai-Kucera).  
> **username_0**: @JoshuaGrochow Thanks for your insightful comments. What is your personal opinion? Do you have any reason to believe that GI is not in P? BTW, I find it terribly amazing that we don't know why there is no known PTIME Turing reduction from GI to GA.  
> **username_5**: @JoshuaGrochow I was wondering if anyone had coded Babai-Luks. Yes, NAUTY in practice is faster than black-box, but NAUTY could benefit from only querying each primal permutation group at most once.  
> **username_6**: @ChadBrewbaker: Sorry, I may have been reading too far between the lines of your question. As far as I know, Babai-Luks has not been coded up. Does nauty even have routines for *just* testing GA, rather than for computing generators of Aut(G) (the latter being equivalent to GI)? I think it just so completely avoids the black-box permutation-querying approach that I'm not sure if nauty would benefit as you suggest.  
> **username_6**: @MohammadAl-Turkistany: this question has made me think more deeply about my beliefs on the complexity of GI. Re: your other question, note that if there is no poly-time Turing (or even many-one) reduction from GI to GA then P$\neq$NP.  
> **username_5**: @JoshuaGrochow correct, NAUTY does a DFS to put each graph in a canonical permutation; saving automorphisms as it goes. CAGES does a great job explaining it, http://www.math.mtu.edu/~kreher/cages.html  

---

### Answer by username_0 on 2015-08-03. Score: 10

Kozen in his paper, [A clique problem equivalent to graph isomorphism](http://dl.acm.org/citation.cfm?id=990529), gives an evidence that $GI$ is not in $P$. The following is from the paper:

> "Nevertheless, it is likely that finding a polynomial time algorithm for graph isomorphism will be as difficult as finding a polynomial time algorithm for an NP-complete problem. In support of this claim, we give a problem equivalent to graph isomorphism, a small perturbation of which is NP-complete."

Also, Babai in his recent breakthrough paper [Graph Isomorphism in quasipolynomial time](http://arxiv.org/abs/1512.03547) gives an argument against the existence of efficient algorithms for GI. He observes that the group isomorphism problem (which is reducible to GI) is a major obstacle to placing GI in $P$. Group Isomorphism problem ( groups are given by their Cayley tableis) is solvable in $n^{O(\log n)}$ and it is not known to be in $P$.

Here is an excerpt from Babai's paper:

> The result of the present paper amplifies the significance of the Group Isomorphism problem (and the challenge problem stated) as a barrier to placing GI in P. It is quite possible that the intermediate status of GI (neither NP-complete, nor polynomial time) will persist.

> **Comments:**
> **username_6**: From Kozen's Lem. 3 one can get a simpler example of this phenomenon: namely, Induced Subgraph Isomorphism (is $H$ an induced subgraph of $G$) is exactly GI when $|G|=|H|$, but is NP-hard when $|G|=c|H|$ for any $c > 1$. For discrete parameters, we know there are problems in P that quickly become NP-complete (e.g. 2SAT vs 3SAT). Do you know if there are examples of problems in P with some continuous parameter that become NP-complete at a sharp threshold? If so, then this kind of reasoning wouldn't be much evidence that GI isn't in P, but I can't think of such an example off the top of my head.  
> **username_0**: @JoshuaGrochow No, I am not aware of any such decision problems. But for optimization problems I know that finding an assignment satisfying $7/8$ of the clauses is in $P$ while finding an assignment satisfying $7/8+ϵ$  of the clauses is $NP$-hard even for satisfiable 3SAT formulas ($ϵ>0$ ).  
> **username_0**: Oops, Klimpel's answer already contains the group isomorphism evidence. Anyway, it is useful to have Babai's perspective on the matter.  
> **username_7**: [Babai retracted the claim of quasipolynomial runtime](http://people.cs.uchicago.edu/~laci/update.html). Apparently there was an error in the analysis.  

---

### Answer by username_2 on 2015-08-04. Score: 6

here are other results not cited yet

* [On the hardness of Graph Isomorphism](http://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.190/Mitarbeiter/toran/hard.pdf) / Torán
  FOCS 2000 and SIAM J. Comput. 33, 5 1093-1108.

  > We show that the graph isomorphism problem is hard under DLOGTIME uniform AC0 many-one reductions for the complexity classes NL, PL (probabilistic logarithmic space) for every logarithmic space modular class ModkL and for the class DET of problems NC1 reducible to the determinant. These are the strongest known hardness results for the graph isomorphism problem and imply a randomized logarithmic space reduction from the perfect matching problem to graph isomorphism. We also investigate hardness results for the graph automorphism problem.
* [Graph Isomorphism is not AC0 reducible to Group Isomorphism](http://eccc.hpi-web.de/report/2010/117/download/) / Chattopadhyay, Toran, Wagner

  > We give a new upper bound for the Group and Quasigroup Isomorphism problems when the input structures are given explicitly by multiplication tables. We show that these problems can be computed by polynomial size nondeterministic circuits of unbounded fan-in with O(log log n) depth and O(log2 n) nondeterministic bits, where n is the number of group elements. This improves the existing upper bound from [Wol94] for the problems. In the previous upper bound the circuits have bounded fanin but depth O(log2 n) and also O(log2 n) nondeterministic bits. We then prove that the kind of circuits from our upper bound cannot compute the Parity function. Since Parity is AC0 reducible to Graph Isomorphism, this implies that Graph Isomorphism is strictly harder than Group or Quasigroup Isomorphism under the ordering defined by AC0 reductions.

> **Comments:**
> **username_6**: Although these are indeed the strongest known lower bounds on GI, they don't really say anything about its not being in P. In the first case, DET isn't so close to P. In the second case, note that the structure of the $\mathsf{AC}^0$-degrees within P is already quite rich.  
> **username_2**: re "strongest known lower bounds on GI", ofc GI is in NP so an actual proof that GI is not in P is equivalent to P≠NP! (possibly via [NPI](https://en.wikipedia.org/wiki/NP-intermediate)≠∅)...  
> **username_6**: Yes, but, for example, it would be nice to know that GI is P-hard! (Of course, P-hardness has very little to do with showing that something is not in P, but it would at least suggest that GI is not in NC!)  

---

