The groups of Richard Thompson and complexity

Research output: Contribution to journalArticlepeer-review

33 Scopus citations


We prove new results about the remarkable infinite simple groups introduced by Richard Thompson in the 1960s. We give a faithful representation in the Cuntz C*-algebra. For the finitely presented simple group V we show that the word-length and the table size satisfy an n log n relation. We show that the word problem of V belongs to the parallel complexity class AC1 (a subclass of P), whereas the generalized word problem of V is undecidable. We study the distortion functions of V and show that V contains all finite direct products of finitely generated free groups as subgroups with linear distortion. As a consequence, up to polynomial equivalence of functions, the following three sets are the same: the set of distortions of V, the set of Dehn functions of finitely presented groups, and the set of time complexity functions of nondeterministic Turing machines.

Original languageEnglish (US)
Pages (from-to)569-626
Number of pages58
JournalInternational Journal of Algebra and Computation
Issue number5-6
StatePublished - 2004

All Science Journal Classification (ASJC) codes

  • Mathematics(all)


  • Complexity
  • Cuntz algebras
  • Distortion
  • R. Thompson groups
  • Word-length

Fingerprint Dive into the research topics of 'The groups of Richard Thompson and complexity'. Together they form a unique fingerprint.

Cite this