有限群上几个问题的算法及复杂度分析

本文讨论有限群上几个计算问题。我们设了一个O(n~2)时间的算法去查找n阶Abel群的基底(把n阶Abel群分解为循环P群的直积)。给出了复杂度为O(n~2log_2n)的n阶Abel群的检验算法。证明了n阶Abel群的同构检验可在O(nlOg_2n)时间内完成。最后,我们讨论定义在有限群上的旅行售货员问题:证明了该问题是NP完全的,并给出了一个O(m·n~2·2~n)时间的算法求解它。