论文标题
组中算法问题的线性平均案例复杂性
Linear average-case complexity of algorithmic problems in groups
论文作者
论文摘要
长期以来，研究了群体理论算法的最严重复杂性。最近引入和研究了随机输入的通用案例复杂性或复杂性。在本文中，我们解决了几类组中单词问题的平均时间复杂性，并表明通常相对于输入单词的长度是线性的，通常是这种情况。我们考虑的组类别包括矩阵组的矩阵（尤其是多环类），一些可解决的组类别以及免费产品。在此过程中，我们在矩阵组中，特别是在nilpotent组中提高了单词问题的最严重复杂性的几个范围。对于免费产品，我们还解决了亚组会员问题的平均案例复杂性，并表明它通常也是线性的。最后，我们讨论了以前尚未考虑的身份问题的复杂性。
The worst-case complexity of group-theoretic algorithms has been studied for a long time. Generic-case complexity, or complexity on random inputs, was introduced and studied relatively recently. In this paper, we address the average-case time complexity of the word problem in several classes of groups and show that it is often the case that the average-case complexity is linear with respect to the length of an input word. The classes of groups that we consider include groups of matrices over rationals (in particular, polycyclic groups), some classes of solvable groups, as well as free products. Along the way, we improve several bounds for the worst-case complexity of the word problem in groups of matrices, in particular in nilpotent groups. For free products, we also address the average-case complexity of the subgroup membership problem and show that it is often linear, too. Finally, we discuss complexity of the identity problem that has not been considered before.
