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.
Original language | English (US) |
---|---|
Pages (from-to) | 343-359 |
Number of pages | 17 |
Journal | Advances in Mathematics |
Volume | 190 |
Issue number | 2 |
DOIs | |
State | Published - Jan 30 2005 |
Externally published | Yes |
Keywords
- Average-case complexity
- Decision problems
- Finitely presented groups
- Generic-case complexity
ASJC Scopus subject areas
- Mathematics(all)