Average-case complexity and decision problems in group theory |
| |
Authors: | Ilya Kapovich Alexei Myasnikov Paul Schupp Vladimir Shpilrain |
| |
Affiliation: | a Department of Mathematics, University of Illinois at Urbana-Champaign, 1409 West Green Street, Urbana, IL 61801, USA;b Department of Mathematics, The City College of New York, New York, NY 10031, USA |
| |
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. |
| |
Keywords: | Average-case complexity Generic-case complexity Decision problems Finitely presented groups |
本文献已被 ScienceDirect 等数据库收录! |
|