Group isomorphism problem

Definition

The group isomorphism problem refers to a general class of problems where two groups are specified using suitable group description rules, and we need to determine whether the groups are isomorphic groups. In some versions, an explicit isomorphism, or a recipe for constructing an isomorphism (for instance, by specifying a bijection for generating sets), may be output if there does exist an isomorphism.

Solution

For black-box groups

See black-box group algorithm for group isomorphism problem. The best known algorithm has order $O(N^{O(\log N)})$ where $N$ is the order of the groups in the worst case. However, the actual bound is based on the minimum size of generating set, and thus, for families of groups that have a bounded number of generators, the best known algorithm is polynomial in the size of the group.

For particular types of groups

For finite abelian groups, there are a number of quick algorithms that work if we can do certain kinds of operations:

• Algorithm for group isomorphism problem for abelian groups based on order statistics: This takes time $O(N^{2})$ times the time for group operations in the black-box case, plus the time taken for enumeration of all elements. If we have a solution for the element order-finding problem, then it can proceed with $O(N)$ calls to that algorithm along with the time for group enumeration, up to some multiplicative polylogarithmic factors.