Generic-case complexity, decision problems in group theory and random walks
<|reference_start|>Generic-case complexity, decision problems in group theory and random walks: 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.<|reference_end|>
@article{kapovich2002generic-case,
    title={Generic-case complexity, decision problems in group theory and random
  walks},
    author={Ilya Kapovich, Alexei Myasnikov, Paul Schupp and Vladimir Shpilrain},
    journal={arXiv preprint arXiv:math/0203239},
    year={2002},
    archivePrefix={arXiv},
    eprint={math/0203239},
    primaryClass={math.GR cs.CC}
}