Generic-case complexity, decision problems in group theory and random walks

2002/03/22 by Ilya Kapovich, Alexei Myasnikov, Kapovich, Ilya +6 · 1 citation
Computer Science · Mathematics · #20F #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Finite Group Theory Research #Geometric and Algebraic Topology #Group Theory (math.GR) #cs.CC #math.GR #msc:20F #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.math/0203239

Revised version

openalex publication_date 2002/03/22 · arxiv created 2002/06/10 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We give a precise definition of ``generic-case complexity'' and show that for a very large class of finitely generated groups the classical decision problems of group theory - the word, conjugacy and membership problems - all have linear-time generic-case complexity. We prove such theorems by using the theory of random walks on regular graphs.

Cited by

• Automorphic orbits in free groups: recent progress

Related

• Average-case complexity and decision problems in group theory
• Complexity of some algorithmic problems in groups: a survey
• Linear average-case complexity of algorithmic problems in groups
• A Finitely presented group whose word problem has sampleable hard instances
• Generic-case complexity of Whitehead's algorithm, revisited