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

Ilya Kapovich; Alexei Myasnikov; Paul Schupp; Vladimir Shpilrain

doi:10.1016/S0021-8693(03)00167-4

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

Ilya Kapovich, Alexei Myasnikov, Paul Schupp, Vladimir Shpilrain

Department of Mathematical Sciences

Research output: Contribution to journal › Article › peer-review

171 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 language	English
Pages (from-to)	665-694
Number of pages	30
Journal	Journal of Algebra
Volume	264
Issue number	2
DOIs	https://doi.org/10.1016/S0021-8693(03)00167-4
State	Published - 15 Jun 2003

Access to Document

10.1016/S0021-8693(03)00167-4

Cite this

@article{5646bc307ebc4b1d93c614c96a584aa8,

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

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.",

author = "Ilya Kapovich and Alexei Myasnikov and Paul Schupp and Vladimir Shpilrain",

year = "2003",

month = jun,

day = "15",

doi = "10.1016/S0021-8693(03)00167-4",

language = "English",

volume = "264",

pages = "665--694",

number = "2",

}

TY - JOUR

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

AU - Kapovich, Ilya

AU - Myasnikov, Alexei

AU - Schupp, Paul

AU - Shpilrain, Vladimir

PY - 2003/6/15

Y1 - 2003/6/15

N2 - 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.

AB - 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.

UR - https://www.scopus.com/pages/publications/0037673298

UR - https://www.scopus.com/inward/citedby.url?scp=0037673298&partnerID=8YFLogxK

U2 - 10.1016/S0021-8693(03)00167-4

DO - 10.1016/S0021-8693(03)00167-4

M3 - Article

AN - SCOPUS:0037673298

SN - 0021-8693

VL - 264

SP - 665

EP - 694

JO - Journal of Algebra

JF - Journal of Algebra

IS - 2

ER -

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

Abstract

Access to Document

Other files and links

Fingerprint

Cite this