Asymptotic invariants, complexity of groups and related problems
arXiv:1012.1325
Abstract
We survey results about computational complexity of the word problem in groups, Dehn functions of groups and related problems.
86 pages. Preliminary version, comments are welcome. v2: some references added, misprints fixed, some changes suggested by the readers are made. 88 pages. v3: more readers' suggestions implemented, index added, the list of references improved. This version is submitted to a journal. v4: The paper is accepted in Bulletin of Mathematical Sciences