کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
9518009 | 1633860 | 2005 | 17 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Average-case complexity and decision problems in group theory
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات (عمومی)
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
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.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Advances in Mathematics - Volume 190, Issue 2, 30 January 2005, Pages 343-359
Journal: Advances in Mathematics - Volume 190, Issue 2, 30 January 2005, Pages 343-359
نویسندگان
Ilya Kapovich, Alexei Myasnikov, Paul Schupp, Vladimir Shpilrain,