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 ?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?)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 groupComplexity of computing the minimum degree of a faithful linear representation of a finite group
Constructing inequivalent irreps of finite groupsConstructing inequivalent irreps of finite groups
Recovering representation from its characterRecovering representation from its character
