New results are presented about the remarkable infinite simple group V
introduced by Richard Thompson in the 1960s. The Thompson group V is
defined as a partial action, and has a faithful representation in a Cuntz
C* algebra (which is a simple algebra).
The word-length and the table size of the elements of V satisfy an n log n
relation (just like the symmetric groups). The word problem of V is easily
decided (in parallel complexity AC1, hence in P), but the generalized word
problem is undecidable. Moreover, up to polynomial equivalence of functions,
the following three sets are the same: the set of distortions of V, the set
of all Dehn functions of finitely presented groups, and the set of time
complexity functions of nondeterministic Turing machines.
Sponsored in part by the FCT approved projects POCTI 32817/99 and POCTI/MAT/37670/2001 in participation with the European Community Fund FEDER and by FCT through Centro de Matemática da Universidade do Porto. Also sponsored in part by FCT, the Faculdade de Ciências da Universidade do Porto, Programa Operacional Ciência, Tecnologia, Inovação do Quadro Comunitário de Apoio III, and by Caixa Geral de Depósitos.