On the Complexity of Group Isomorphism.
Fabian Wagner · Electronic colloquium on computational complexity · 2011
The group isomorphism problem consists in deciding whether two groups G and H given by their multiplication tables are isomorphic. An algorithm for group isomorphism attributed to Tarjan runs in time n, c.f. [Mil78]. Miller and Monk showed in [Mil79] that group isomorphism can be many-one reduced to isomorphism testing for directed graphs. For groups with n elements, the graphs have valence at least n. We introduce a different reduction for isomorphism testing, where the valence of the graphs, say X(G) and X(H), and the complexity of the isomorphism test is closely related to the structure of the groups. Let G be the class of groups having a composition series where composition factors of size at least logn/ log logn come before the others. The composition series isomorphism problem is given two composition series S for G and S′ for H, such that any subgroup of G according to S is mapped blockwise onto that of H according to S′. In the reduction onto graph isomorphism, we get graphs X(G,S) and X(H,S′). Then for p-groups we find such an isomorphism in time n and for the more general class of G-groups in time n logn/ log logn for a constant c. We analyze the time complexity for three isomorphism testing algorithms with respect to two parameters β, γ which depend on the group structure. With a combination of the algorithms we also can show that G-group isomorphism is in time n β+logn/ log , and p-group isomorphism is in time n β) with β, γ ≤ logp n. Most recently, D. Rosenbaum improves in [Ros12] these bounds to n logn+O(1) for p-groups and nilpotent groups, and to n logn+O(logn/ log logn) for solvable groups.