Finding an isomorphism requires to show that for 2 groups $G$ and $H$, there exists a bijective map $\phi : G\to H$ such that $$\phi(ab)=\phi(a)\phi(b)$$ For all $a,b \in G$. This is (probably naively) pretty straight forward, and there are plenty of theorems that allow us to show that groups of specific orders must be isomorphic to some specific set of groups. So, my question (which I hope isn’t too loaded) is
What intrinsically makes finding if 2 groups are isomorphic so hard? Is it showing that they are bijective, is it showing that they are operation preserving, or is it something entirely different?
There are two variants of Group Isomorphism (GpI):
It is known that (under polynomial-time computable, and even $\textsf{AC}^{0}$-computable reductions) that:
While GI is known to be in $\textsf{NP} \cap \textsf{coAM}$, the best upper bound we have for SuccinctGpI is $\textsf{Promise}\Sigma_{2}^{p}$. In the setting of black-box groups, even verifying the group axioms is a $\Pi_{2}^{p}$-problem- so we need a promise that the inputs are groups. If you are working with permutation or matrix groups, then you get a better upper bound of $\Sigma_{2}^{p}$. In the multiplication table setting, we can check the group axioms in $\textsf{AC}^{0}$.
In the CayleyGpI setting, we have the generator enumeration algorithm. Every finite group has a generating set of size at most $\log n$. So compute a generating set $S$ for $G$, and check all ways of embedding $S$ into $H$. Do any of those extend to an isomorphism? This check takes $n^{\log n + O(1)}$ time. (Note that if a group has a bounded number of generators, this check takes polynomial time). Rosenbaum and Wagner improved this to $n^{(1/2) \log n + O(1)}$ using composition-series enumeration. In the case of solvable groups, they get $n^{(1/4) \log n + O(1)}$ using a technique called bidirectional collision.
The Computational Group Theory community has done very impressive work on SuccinctGpI. Even their techniques, however, do not beat $|G|^{\Theta(\log |G|)}$ in the worst case (where here, I stress $|G|$ to be the order of the group, and not the size of the succinct input which is $O(\log |G|)$).
For some intuition on why the model is important, consider the case of groups of cube-free order. These groups have generating sets of size $3$. So for CayleyGpI, this problem is solvable in polynomial-time. On the other hand, placing this problem into $\textsf{P}$ in the permutation group setting took work. See this recent result of Dietrich & Wilson (https://arxiv.org/abs/1810.03467).
Another piece of intuition is that constructive recognition of finite simple groups is hard in the succinct setting. See for instance: