Complexity of establishing finite groups (non)-isomorphism ?

Question

Question Given two finite groups G and H of the same order N what are the algorithms and what is their complexity (in terms of N) to check is G isomorphic to H or not ? Is there polynomial in N algorithm ?

Details Assume groups are given in the form of Cayley tables, we know the identity elements and inverses are known to us.

The complexity can be measured as "worst case" or "average" (in some sense of averaging) - I am interested in both, but primarily in "worst case".

By complexity I mean the count of the number of operations, there are some details in definition but I think they will not affect the answer essentially.

---

Naive exponential time algorithm Just consider all possible set-theoretic bijections between G and H and for each bijection check whether Cayley table is the same or not. Number of bijections is N! so worst case complexity is exponential.

---

For abelian groups seems linear time (=O(N)) algorithm seems exists:

---

Related:

Algorithm to check is representation irreducible ? Algorithm to decompose the reducible one ?

How to compute all irreducible representations of a finite group ? (how GAP is doing this?)

Complexity of computing the minimum degree of a faithful linear representation of a finite group

Constructing inequivalent irreps of finite groups

Recovering representation from its character

Answer 1

It is unknown whether this problem is polynomial. It is at worst $O(N^{\log N})$. To see that, observe that the group can be generated by at most $\log N$ elements, a homomorphism is determined by the images of its generators, and deciding whether a specific collection of images defines an isomorphism is polynomial (and fast in practice using defining relations for the group).

The hardest examples are likely to be $p$-groups (of class 2 or more) with about $O(\log N)$ generators, and I would guess that there is no way of doing that that is significantly faster than $O(N^{\log N})$.

Answer 2

I agree w/ Holt's technical statements (not sure whether I agree about his guess on the final running time, though I agree about which groups are likely to be hardest). But I wanted to add that a lot of work has been done on this question, and provide links to the works I know of that get time polynomial in the order of the group (or close to it).

In addition to Abelian groups (mentioned in the OQ), for the following classes of groups, isomorphism can be solved in time polynomial in the order of the group. In several cases the works I cite are the end of a line of several papers by many authors; see the papers linked here for citations/history.

• Groups without Abelian normal subgroups (aka Fitting-free): Babai-Codenotti-Qiao
• $p$-groups of class 2, exponent $p$, and either (a) genus 2 (Brooksbank-Maglione-Wilson) or (b) quotient of genus 1 (Lewis-Wilson) (in Schrock's thesis, he did work towards uniting these to quotients of genus 2). (These algorithms are even more efficient, and work in the realistic, succinct models where the groups are given by matrices or other kinds of generators.)
• Groups with Abelian Sylow towers (Babai-Qiao), or more generally tame extensions (Grochow-Qiao, arXiv version)
• Groups of cube-free order Dietrich-Wilson, even polynomial time in the input size when the groups are given by generating sets of permutations
• For a certain natural distribution of random $p$-groups of class 2 and exponent $p$ Brooksbank-Li-Qiao-Wilson
• Groups of almost all orders Dietrich-Wilson arXiv version

Some further results:

• For groups in which the solvable radical is either contained in the center or elementary Abelian, the isomorphism problem can be solved in $N^{O(\log \log N)}$ time Grochow-Qiao.
• Hamiltonian groups in linear time in the order of the groups Das-Sharma, and more generally Abelian direct product with a group of bounded order in nearly-linear time.
• Direct product groups can be decomposed into their direct factors efficiently. This was done in the Cayley table model by Kayal-Nezhmetdinov, and in the stronger model where groups are given by generating permutations by James B. Wilson (part I here)