Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
9518009 | Advances in Mathematics | 2005 | 17 Pages |
Abstract
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 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 of G is linear time, uniformly with respect to the collection of all length-invariant measures on G. This results applies to many of the groups usually studied in geometric group theory: for example, all braid groups Bn, all groups of hyperbolic knots, many Coxeter groups and all Artin groups of extra-large type.
Related Topics
Physical Sciences and Engineering
Mathematics
Mathematics (General)
Authors
Ilya Kapovich, Alexei Myasnikov, Paul Schupp, Vladimir Shpilrain,