Algorithmic theory of free solvable groups: Randomized computations

详细信息    查看全文

• 作者：Alexander Ushakov¹ ; ² ; ^{aushakov@stevens.edu" class="auth_mail}
• 关键词：03D15 ; 20F65 ; 20F10
• 刊名：Journal of Algebra
• 出版年：1 June 2014
• 年：2014
• 卷：407
• 期：Complete
• 页码：178-200
• 全文大小：383 K

文摘

We design new deterministic and randomized algorithms for computational problems in free solvable groups. In particular, we prove that the word problem and the power problem can be solved in quasi-linear time and the conjugacy problem can be solved in quasi-quartic time by Monte Carlo type algorithms.