Linear average-case complexity of algorithmic problems in groups
From MaRDI portal
Publication:6505887
arXiv2205.05232MaRDI QIDQ6505887FDOQ6505887
Authors: Alexander Y. Olshanskii, Vladimir Shpilrain 
Abstract: 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.
Analysis of algorithms and problem complexity (68Q25) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10)
This page was built for publication: Linear average-case complexity of algorithmic problems in groups
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6505887)
