What evidence is there that Graph Isomorphism is not in $P$?

Question

Motivated by Fortnow's comment on my post, 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" 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$?

Answer 1

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:

1. The Group Isomorphism Problem: A Possible Polymath Problem?
2. Advances on Group Isomorphism
3. 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.

Answer 2

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.

Answer 3

Kozen in his paper, A clique problem equivalent to graph isomorphism, 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 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.

Answer 4

here are other results not cited yet

• On the hardness of Graph Isomorphism / Torán FOCS 2000 and SIAM J. Comput. 33, 5 1093-1108.

  We show that the graph isomorphism problem is hard under DLOGTIME uniform AC⁰ many-one reductions for the complexity classes NL, PL (probabilistic logarithmic space) for every logarithmic space modular class Mod_kL and for the class DET of problems NC¹ 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 AC⁰ reducible to Group Isomorphism / 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(log² 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² n) and also O(log² n) nondeterministic bits. We then prove that the kind of circuits from our upper bound cannot compute the Parity function. Since Parity is AC⁰ reducible to Graph Isomorphism, this implies that Graph Isomorphism is strictly harder than Group or Quasigroup Isomorphism under the ordering defined by AC⁰ reductions.