Beating the generator-enumeration bound for p-group isomorphism
Beating the generator-enumeration bound for p-group isomorphism
复制标题
打破 p 群同构的生成器枚举界限
DOI：
10.1016/j.tcs.2015.05.036
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Fabian Wagner
中科院分区：
文献类型：
--
作者：
David J. Rosenbaum;Fabian Wagner
考虑群同构问题：给定两个由乘法表指定的有限群G和H，判定G是否∈ H。几十年来，n log p <$n+ O（1）生成元计数界（其中p是划分群阶的最小素数）一直是一般群的最佳最坏情况结果。在这项工作中，我们证明了一个改进的生成元计数界的p-群，这被认为是困难的情况下，组同构问题。我们首先给出从群同构到n（1/2）logp <$n+ O（1）个p-群合成-级数同构的图灵约化。通过给出p-群合成-级数同构到度至多为p+ O（1）的图的同构检验的Karp约化，并应用有界度图的同构检验算法，得到了p-群合成-级数同构的一个n O（p）时间算法.结合这两个结果，得到一个p-群同构的算法，它至多需要n（1/2）log p <$n+ O（p）时间。该算法在p较小时比生成枚举算法快，在p较大时比生成枚举算法慢。选择基于p和n的更快算法，得到p-群同构的n（1/2+ o（1））log n的上界。
We consider the group isomorphism problem: given two finite groups G and H specified by their multiplication tables, decide if G≅ H. For several decades, the n log p n+ O (1) generator-enumeration bound (where p is the smallest prime dividing the order of the group) has been the best worst-case result for general groups. In this work, we show an improvement over the generator-enumeration bound for p-groups, which are believed to be the hard case of the group isomorphism problem. We start by giving a Turing reduction from group isomorphism to n (1/2) log p n+ O (1) instances of p-group composition-series isomorphism. By showing a Karp reduction from p-group composition-series isomorphism to testing isomorphism of graphs of degree at most p+ O (1) and applying algorithms for testing isomorphism of graphs of bounded degree, we obtain an n O (p) time algorithm for p-group composition-series isomorphism. Combining these two results yields an algorithm for p-group isomorphism that takes at most n (1/2) log p n+ O (p) time. This algorithm is faster than generator-enumeration when p is small and slower when p is large. Choosing the faster algorithm based on p and n yields an upper bound of n (1/2+ o (1)) log n for p-group isomorphism.