Average-case complexity and decision problems in group theory

Ilya Kapovich, Alexei Myasnikov, Paul Schupp, Vladimir Shpilrain

Research output: Contribution to journalArticlepeer-review

52 Scopus citations

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 languageEnglish
Pages (from-to)343-359
Number of pages17
JournalAdvances in Mathematics
Volume190
Issue number2
DOIs
StatePublished - 30 Jan 2005

Keywords

  • Average-case complexity
  • Decision problems
  • Finitely presented groups
  • Generic-case complexity

Fingerprint

Dive into the research topics of 'Average-case complexity and decision problems in group theory'. Together they form a unique fingerprint.

Cite this