Polynomial-Time Isomorphism Test for Groups with No Abelian Normal Subgroups - (Extended Abstract)
Polynomial-Time Isomorphism Test for Groups with No Abelian Normal Subgroups - (Extended Abstract)
复制标题
没有阿贝尔正规子群的群的多项式时间同构检验 -（扩展摘要）
DOI：
10.1007/978-3-642-31594-7_5
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
Youming Qiao
中科院分区：
文献类型：
--
作者：
L. Babai;Paolo Codenotti;Youming Qiao
我们考虑由Cayley表给出的n阶群同构的检验问题。在过去的四十年里，一般情况下的时间复杂度上的平凡nlogn界限没有得到改善。我们证明，有效的算法的障碍是阿贝尔正常子群的存在下，我们表明这给一个多项式时间同构测试组没有非平凡的阿贝尔正常子群。这结束了一个由作者和J. A。Grochow（SODA 2011）。两个关键的新成分是：（a）测试置换群在时间上的置换同构、在阶上的多项式和在阶上的简单指数的算法;（B）“扭曲码等价问题”的引入，通过承认字母表上的群作用来推广经典码等价问题。这两个问题是独立的利益。
We consider the problem of testing isomorphism of groups of order n given by Cayley tables. The trivial nlogn bound on the time complexity for the general case has not been improved upon over the past four decades. We demonstrate that the obstacle to efficient algorithms is the presence of abelian normal subgroups; we show this by giving a polynomial-time isomorphism test for groups without nontrivial abelian normal subgroups. This concludes a project started by the authors and J. A. Grochow (SODA 2011). Two key new ingredient are: (a) an algorithm to test permutational isomorphism of permutation groups in time, polynomial in the order and simply exponential in the degree; (b) the introduction of the "twisted code equivalence problem," a generalization of the classical code equivalence problem by admitting a group action on the alphabet. Both of these problems are of independent interest.