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

Ilya Kapovich, Alexei Myasnikov, Paul Schupp, Vladimir Shpilrain

Research output: Contribution to journalArticlepeer-review

165 Scopus citations

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.

Original languageEnglish
Pages (from-to)665-694
Number of pages30
JournalJournal of Algebra
Volume264
Issue number2
DOIs
StatePublished - 15 Jun 2003

Fingerprint

Dive into the research topics of 'Generic-case complexity, decision problems in group theory, and random walks'. Together they form a unique fingerprint.

Cite this