论文标题
对于大多数订单而言，小组同构是几乎是线性的时间
Group isomorphism is nearly-linear time for most orders
论文作者
论文摘要
We show that there is a dense set $\ourset\subseteq \mathbb{N}$ of group orders and a constant $c$ such that for every $n\in \ourset$ we can decide in time $O(n^2(\log n)^c)$ whether two $n\times n$ multiplication tables describe isomorphic groups of order $n$.这比一般的$ n^{o（\ log n）} $ - 时间复杂性大大改善，并表明几乎所有组订单$ n $都可以有效地测试组同构。我们还显示时间$ O（n^2 （\ log n）^c）$可以确定是否描述了一个组；这比已知的$ O（n^3）$复杂性有所改善。我们的复杂性是针对确定性的多磁带图灵机模型计算的。我们在承诺层次结构中也赋予了RAM模型。
We show that there is a dense set $\ourset\subseteq \mathbb{N}$ of group orders and a constant $c$ such that for every $n\in \ourset$ we can decide in time $O(n^2(\log n)^c)$ whether two $n\times 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)^c)$ it can be decided whether an $n\times n$ multiplication table describes a group; this improves over the known $O(n^3)$ 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.
