Average-case complexity and decision problems in group theory
<|reference_start|>Average-case complexity and decision problems in group theory: We investigate the average-case complexity of decision problems for finitely generated groups, in particular the word and membership problems. Using our recent results on ``generic-case complexity'' we show that if a finitely generated group $G$ has the word problem solvable in subexponential time and has a subgroup of finite index which possesses a non-elementary word-hyperbolic quotient group, then the average-case complexity of the word problem for $G$ is linear time, uniformly with respect to the collection of all length-invariant measures on $G$. For example, the result applies to all braid groups $B_n$.<|reference_end|>
@article{kapovich2002average-case,
    title={Average-case complexity and decision problems in group theory},
    author={Ilya Kapovich, Alexei Myasnikov, Paul Schupp and Vladimir Shpilrain},
    journal={arXiv preprint arXiv:math/0206273},
    year={2002},
    archivePrefix={arXiv},
    eprint={math/0206273},
    primaryClass={math.GR cs.CC math.GT}
}