Linear average-case complexity of algorithmic problems in groups

DOI10.1016/J.JALGEBRA.2025.01.013MaRDI QIDQ7008558zbMATH OpenFDO

Authors Alexander Y. Olshanskii, Vladimir Shpilrain

Publication date 21 March 2025

Published in Journal of Algebra (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.JALGEBRA.2025.01.013

zbMATH Keywords

average-case complexitymatrix groupnilpotent groupword problem

Mathematics Subject Classification ID

Computational methods for problems pertaining to group theory (20-08) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Nilpotent groups (20F18) Other matrix groups over fields (20H20) Analysis of algorithms and problem complexity (68Q25)

Review text

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.

Cites work

• Algorithmic problems for metabelian groups
• Algorithmic theory of free solvable groups: randomized computations.
• Algorithmically complex residually finite groups
• Average Case Complete Problems
• Average-case complexity and decision problems in group theory.
• Braid groups are linear
• Braid groups are linear
• Cogrowth and amenability of discrete groups
• Fast multiplication of large numbers
• FOLDINGS, GRAPHS OF GROUPS AND THE MEMBERSHIP PROBLEM
• Generic-case complexity, decision problems in group theory, and random walks.
• Geometry of the conjugacy problem in lamplighter groups
• Groups of polynomial growth and expanding maps. Appendix by Jacques Tits
• scientific article; zbMATH DE number 3746135 (Why is no real title available?)
• scientific article; zbMATH DE number 3762288 (Why is no real title available?)
• scientific article; zbMATH DE number 3779604 (Why is no real title available?)
• scientific article; zbMATH DE number 51735 (Why is no real title available?)
• scientific article; zbMATH DE number 3574107 (Why is no real title available?)
• scientific article; zbMATH DE number 3440002 (Why is no real title available?)
• scientific article; zbMATH DE number 1836314 (Why is no real title available?)
• Integer multiplication in time \(O(n\log n)\)
• Introductory notes on Richard Thompson's groups
• Isoperimetric functions of groups and computational complexity of the word problem
• Logspace and compressed-word computations in nilpotent groups
• On finitely generated soluble linear groups
• On Infinite Soluble Groups (II)
• On one method for fast approximation of zeta constants by rational fractions
• Ramanujan's master theorem
• Random van Kampen diagrams and algorithmic problems in groups.
• Random Walks on Infinite Graphs and Groups
• Shorter Notes: Representations of Polycyclic Groups
• Sublinear time algorithms in the theory of groups and semigroups.
• The Degree of Polynomial Growth of Finitely Generated Nilpotent Groups
• Thompson’s Group and Public Key Cryptography
• Varieties of groups
• Varieties of soluble groups and a dichotomy of P. Hall

Cited in

(1)

• Nearly-linear solution to the word problem for 3-manifold groups

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 Q7008558)