Group isomorphism is nearly-linear time for most orders
share
We show that there is a dense set Υ⊆ℕ of group orders and a constant c such that for every n∈Υ we can decide in time O(n^2(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^2 (log n)^d) it can be decided whether an n× n multiplication table describes a group; this improves over the known O(n^3) complexity.
READ FULL TEXT