Linear average-case complexity of algorithmic problems in groups (Q7008558)

Let \(W_n\) denote the set of all words of length \(n\) over a finite group alphabet. For a word \(w \in W_n\), let \(T(w)\) be the time taken by a deterministic multitape Turing machine algorithm \(A\) to process the input \(w\). Then the average-case time complexity of \(A\) on inputs of length \(n\) is defined as\N\[\N\frac{1}{|W_n|} \sum_{w \in W_n} T(w).\N\]\NThis paper investigates the average-case complexity (as opposed to worst-case or generic-case complexity) of fundamental algorithmic problems in group theory, such as the word and subgroup membership problems. The main focus is on finitely generated groups, under the uniform distribution on input words of fixed length.\N\NA central notion is that of a variety \(\mathcal{V}\) of groups, defined as a class of groups satisfying a fixed set of group identities. Varieties are closed under taking subgroups, quotients, and arbitrary direct products.\N\NThe authors prove that for large classes of groups, including all finitely generated groups in a given variety \(\mathcal{V}\), the average-case time complexity of the word problem is linear in \(n\). More precisely, this includes the following cases:\N\begin{itemize}\N\item[(i)] Matrix groups over \(\mathbb{Q}\), such as polycyclic and nilpotent groups (Sections 2.1--2.2);\N\item[(ii)] Free solvable groups and, more generally, finitely generated groups in a solvable variety (Section 3);\N\item[(iii)] Thompson's group \(F\) (Section 3.2);\N\item[(iv)] Free products \(A * B\), where both \(A\) and \(B\) have word problems decidable in polynomial time (Section 4);\N\item[(v)] The subgroup membership problem in free products of the type above (Section 5).\N\end{itemize}\NSection 6 addresses the identity problem in a group variety \(\mathcal{V}\). For a word \(w\) over the generators, determine whether \(w=1\) in all groups in \(\mathcal{V}\). The authors prove that if the word problem in \(\mathcal{V}\) has subexponential worst-case complexity, then the average-case complexity of the identity problem is linear.