Group isomorphism problem

From Groupprops
Jump to: navigation, search

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: