Group Isomorphism with Fixed Subnormal Chains
Group Isomorphism with Fixed Subnormal Chains
复制标题
具有固定次正规链的群同构
DOI：
--
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
E. Luks
中科院分区：
文献类型：
--
作者：
E. Luks
在最近的工作中，Rosenbaum和瓦格纳证明了显式列出的n阶p-群的同构可以在n^{frac{1}{2}log_pn + O（p）}$时间内检验，大约是经典界的平方根。$O（p）$项完全是由于在两个群中匹配固定合成序列的同构测试的$n^{O（p）}$成本。在这里，我们专注于固定的组成系列的子问题，并表现出多项式时间的算法，是有效的一般群体。随后的论文将在相同的时间范围内构造标准形式。
In recent work, Rosenbaum and Wagner showed that isomorphism of explicitly listed $p$-groups of order $n$ could be tested in $n^{frac{1}{2}log_p n + O(p)}$ time, roughly a square root of the classical bound. The $O(p)$ term is entirely due to an $n^{O(p)}$ cost of testing for isomorphisms that match fixed composition series in the two groups. We focus here on the fixed-composition-series subproblem and exhibit a polynomial-time algorithm that is valid for general groups. A subsequent paper will construct canonical forms within the same time bound.