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.