AnO(n) Algorithm for Abelianp-Group Isomorphism and anO(n log n) Algorithm for Abelian Group Isomorphism

✍ Scribed by Narayan Vikas

• Publisher: Elsevier Science
• Year: 1996
• Tongue: English
• Weight: 417 KB
• Volume: 53
• Category: Article
• ISSN: 0022-0000
• DOI: 10.1006/jcss.1996.0045

✦ Synopsis

The isomorphism problem for groups is to determine whether two finite groups are isomorphic. The groups are assumed to be represented by their multiplication tables. Tarjan has shown that this problem can be done in time O(n log n + O(1) ) for groups of cardinality n. Savage has claimed an algorithm for showing that if the groups are Abelian, isomorphism can be determined in time O(n 2 ). We improve this bound and give an O(n log n) algorithm for Abelian group isomorphism. Further, we show that if the groups are Abelian p-groups then isomorphism can be determined in time O(n). We also show that the elementary divisor sequence for an Abelian group can be determined in time O(n log n) and for an Abelian p-group it can be determined in time O(n).