Group isomorphism is nearly-linear time for most orders
Group isomorphism is nearly-linear time for most orders
复制标题
对于大多数订单来说，群同构的时间几乎是线性的
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
James B. Wilson
中科院分区：
文献类型：
--
作者：
H. Dietrich;James B. Wilson
我们证明了存在一个稠密的群序集，使得对于每个这样的序，我们可以在近线性的时间内决定是否有两个乘法表描述同构的群。这比一般的拟多项式时间复杂度有了显着的改善，并表明几乎所有的群阶都可以有效地测试群同构。我们还证明了在近线性时间内，可以决定乘法表是否描述一个群；这改进了已知的超线性复杂性。我们的复杂性是针对确定性的多磁带图灵机模型计算的，但我们也给出了对Promise层次结构中的RAM模型的影响。
We show that there is a dense set of group orders such that for every such order we can decide in nearly-linear time whether two multiplication tables describe isomorphic groups. This improves significantly over the general quasi-polynomial time complexity and shows that group isomorphism can be tested efficiently for almost all group orders. We also show that in nearly-linear time it can be decided whether a multiplication table describes a group; this improves over the known super-linear complexity. Our complexities are calculated for a deterministic multi-tape Turing machine model, but we give the implications to a RAM model in the promise hierarchy as well.