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

Mathematics

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

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 (US)
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 - Jun 15 2003

ASJC Scopus subject areas

Algebra and Number Theory

Online availability

10.1016/S0021-8693(03)00167-4

Library availability

Discover UIUC Full Text

Cite this

@article{ff2a92f86d6d4d0fa675c2bddc8eaeed,

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 (US)",

volume = "264",

pages = "665--694",

journal = "Journal of Algebra",

issn = "0021-8693",

publisher = "Academic Press Inc.",

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 - http://www.scopus.com/inward/record.url?scp=0037673298&partnerID=8YFLogxK

UR - http://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

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this