TY - JOUR
T1 - Average-case complexity and decision problems in group theory
AU - Kapovich, Ilya
AU - Myasnikov, Alexei
AU - Schupp, Paul
AU - Shpilrain, Vladimir
PY - 2005/1/30
Y1 - 2005/1/30
N2 - 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.
AB - 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.
KW - Average-case complexity
KW - Decision problems
KW - Finitely presented groups
KW - Generic-case complexity
UR - http://www.scopus.com/inward/record.url?scp=6944252026&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=6944252026&partnerID=8YFLogxK
U2 - 10.1016/j.aim.2003.02.001
DO - 10.1016/j.aim.2003.02.001
M3 - Article
AN - SCOPUS:6944252026
SN - 0001-8708
VL - 190
SP - 343
EP - 359
JO - Advances in Mathematics
JF - Advances in Mathematics
IS - 2
ER -