Group isomorphism is nearly-linear time for most orders

2020/11/05 by Dietrich, Heiko, Wilson, James B. · 1 citation
#20-80 #68Q25 #Computational Complexity (cs.CC) #F.2.2 #FOS: Computer and information sciences #FOS: Mathematics #Group Theory (math.GR) #I.1.2

paper · doi:10.48550/arxiv.2011.03133

Abstract

We show that there is a dense set \ourset⊆ ℕ of group orders and a constant c such that for every n∈ \ourset we can decide in time O(n²(log n)^c) whether two n× n multiplication tables describe isomorphic groups of order n. This improves significantly over the general n^{O(log n)}-time complexity and shows that group isomorphism can be tested efficiently for almost all group orders n. We also show that in time O(n² (log n)^c) it can be decided whether an n× n multiplication table describes a group; this improves over the known O(n³) complexity. Our complexities are calculated for a deterministic multi-tape Turing machine model. We give the implications to a RAM model in the promise hierarchy as well.

Cited by

• On the Parallel Complexity of Identifying Groups and Quasigroups via Decompositions

Related

• Polynomial-time isomorphism testing of groups of most finite orders
• Breaking the n^(log n) Barrier for Solvable-Group Isomorphism
• Group Isomorphism with Fixed Subnormal Chains
• Beating the Generator-Enumeration Bound for p-Group Isomorphism
• On the Parallel Complexity of Identifying Groups and Quasigroups via Decompositions