有限群上几个问题的复杂性分析

本文,我们设计了一个O(n~2)时间的算法,去求n阶Abel群的基底;即把n阶Abel群分解为循环P群的直积。接着,我们讨论有名的群同构检验问题,洪加威O(n)时间的n阶Abel群同构检验算法也列入本文(洪加威教授提供)。最后,我们证明有限群上流动售货员问题是NP-完全的;并给出O(m~2·n·2~m)时间的算法求解这个问题,这里n为群的阶,m为图中结点个数。