What is the hardest instance for the group isomorphism problem?

Question

Two groups $(G,\cdot)$ and $(H, \times)$ are said to be isomorphic iff there exists a homomorphism from $G$ to $H$ which is bijective. The group isomorphism problem is as follows: given two groups, check whether they are isomorphic or not. There are different ways to input a group, the two mostly used are by a Cayley table and by a generating set. Here I am assuming input groups are given by their Cayley table. More formally:

$\textbf{Group Isomorphism Problem}$

$\textbf{Input : }$ Two groups $(G,\cdot)$ and $(H,\times)$.

$\textbf{Decide : } $ Is $G \cong H$?

Let us assume that $n = |G| = |H|$

Group Isomorphism problem when input groups are given by Cayley table is not known to be in $\textbf{P}$ in general. Although there are group classes like the abelian group class for which the problem is known to be in polynomial time, groups which are the extension of an abelian group, simple groups etc. Even for nilpotent class two groups, no algorithm better than brute force is known.

A brute force algorithm for group isomorphism is given by Tarjan, which is as follows. Let $G$ and $H$ are two input groups, and let $S$ be a generating set of the group $G$. It is a well-known fact that every finite group admits a generating set of $\mathcal{O}(\log n)$ size and which can be found in polynomial time. The number of images of the generating set $S$ in the homomorphism from $G$ to $H$ is $n^{\log n}$ many. Now, check whether each possible homomorphism is bijective or not. The overall runtime will be $n^{\log n + \mathcal{O}(1)}$.

Let me first define the center of the group $G$:

$$Z(G) = \{g \in G \mid ag=ga, \forall a \in G\}$$

$Z(G)$ denotes the elements of the group $G$ which commutes with all other elements of the group $G$. Groups for which $G/Z(G)$ ( / used for quotient) is abelian are known as a nilpotent class two groups. To me it appears that nilpotent class two groups are the hardest instances to solve the group isomorphism problem. The meaning of "hardest instances" is: solving that case will allow researchers who work in group theory to solve the isomorphism problem of a large number of groups.

Initially, I thought that simple groups are the hardest instances as they are building blocks of all groups, but later came to know that the isomorphism problem for simple groups is in $\textbf{P}$.

Question: What is the hardest instance for the group isomorphism problem?

Answer 1

$p$-groups of class 2 and exponent $p$ are widely believed to be the hardest case of Group Isomorphism ($p > 2$). (For $p=2$, we need to consider exponent 4, since all groups of exponent 2 are abelian - easy exercise for the reader.) Although there is as yet no reduction from general GpIso to this class of groups (though see point 0.5 below), there are several reasons for this belief. Let me outline some of them here.

0) Practical experience (see papers by Newman, Eick, O'Brien, Holt, Cannon, Wilson, ... which give the algorithms that are implemented in GAP and MAGMA).

0.5) [EDIT: added 8/7/19] Reductions. When such $p$-groups are given by generating sets of matrices over $\mathbb{F}_p$, the problem is $\mathsf{TI}$-complete [G.-Qiao '19]. Also (cf. point (4) below), isomorphism of $p$-groups of exponent $p$ and class $c < p$ reduces in poly time to isomorphism of $p$-groups of exponent $p$ and class 2 (ibid.).

1) Structure (reduce to solvable, then to $p$-group). Every finite group contains a unique maximal solvable normal subgroup, called the solvable radical, denoted $Rad(G)$. $G/Rad(G)$ contains no abelian normal subgroups, and isomorphism of such groups can be handled efficiently in practice (Cannon-Holt J. Symb. Comput. 2003) and in theory (Babai-Codenotti-Qiao ICALP 2012). Even for groups where $Rad(G)$ is abelian, some of these can be handled in $n^{O(\log \log n)}$ time (G-Qiao CCC '14, SICOMP '17) - so, not quite polynomial, but much closer than $n^{\log n}$. The main obstacle thus appears to be solvable (normal sub)groups. Now, within solvable groups, there is a lot of structure - starting with the fact that every solvable group is a knit product of its Sylow $p$-subgroups - and it seems the hardest cases are $p$-groups.

2) Counting. The number of groups of order $n$ is $\leq n^{(\frac{2}{27} + o(1))\mu(n)^2}$, where $\mu(n)$ is the largest exponent of any prime dividing $n$ (Pyber 1993). The number of $p$-groups of order $n=p^m$ is at least $p^{(\frac{2}{27} + o(1))m^2}$ (Higman 1960). So you see that the coefficient of the leading terms in the exponents match. In this sense "most" groups are $p$-groups (even of class 2 and exponent $p$). There is a long-standing conjecture which says that "most" in the preceding weak sense can be strengthened to say that proportion of groups of order $\leq n$ which are $p$-groups tends to 1 as $n \to \infty$.

3) Universality (/wildness). Giving a classification of $p$-groups would imply a classification of all modular representations of any finite group (or even Artinian algebra) in characteristic $p$ (Sergeichuk 1977).

4) Flexibility. Why $p$-groups of class 2 and not higher class? (Note that $p$-groups of nearly-maximal class, so-called "small coclass", have essentially been classified, Eick & Leedham-Green 2006, see also some of the answers here.) To any $p$-group one can associate a graded Lie ring, where bracket in the Lie ring corresponds to commutator in the group. Associativity in the group implies the Jacobi identity for the bracket, thus giving rise to a genuine Lie ring. However, note that when the group is class 2, the Jacobi identity is trivially satisfied (all its terms are automatically 0), so this puts no additional constraints on the structure. It basically just corresponds to an arbitrary skew-symmetric bilinear map. For $p$-groups of exponent $p$, there is even a reduction from class $c < p$ to class 2.