Groups where word problem is solvable, but not quickly?

There is a very nice recent paper "Algorithmically complex residually finite groups" by O. Kharlampovich, A. Myasnikov, and M. Sapir about this issue - containing also many references to earlier results about complex Dehn functions and the complexity of the word problem in specific cases.

Theorem (Kharlampovich, Myasnikov, Sapir) Let $f(n)$ be a recursive function. Then there exists a residually finite finitely presented solvable group G such that for any finite presentation $⟨X;R⟩$ of $G$ the time complexity of both “yes” and “no” parts of the word problem are at least as high as $f(n)$.

The paper also contains examples.


Here's a recipe to produce f.p. groups with solvable word problem at least as hard as the membership problem in any set $A$ of positive integers.

Consider the group $$\Gamma_A=\langle t,x\mid [t^nxt^{-n},x]=1, \forall n\in A\rangle.$$

Then for $n>0$, $[t^nxt^{-n},x]=1$ in $\Gamma_A$ iff $n\in A$. In particular, ($\#$) any algorithm for the word problem in $\Gamma_A$ with complexity $f(n)$ (supremum of halting time for inputs in the $n$-ball) solves the membership problem in $A$ with halting time $\le f(4n+4)$.

The group $\Gamma_A$ has solvable word problem iff $A$ is recursive. So for finitely generated group we are already done with no prerequisites (of course this boils down to the question of complexity of the membership problem in recursive subsets integers, but this is no longer group theory).

Now an adaptation of Higman's embedding theorem by Clapham (C. R. J. Clapham. An embedding theorem for finitely generated groups”, Proc. London. Math. Soc. (3), 17, 1967, 419-430.) yields that every f.g. group with solvable word problem embeds into a finitely presented group with solvable word problem. If we embed $\Gamma_A$ into such a finitely presented group $\Lambda$ and require that $t,x$ are among a generating subset, then ($\#$) above also holds in $\Lambda$.

The case of residually finite finitely presented groups is considerably harder and is addressed by the Kharlampovich-Myasnikov-Sapir paper referenced in Andreas Thom's answer.


A likely example is given by Cremona groups, as in this paper by Serge Cantat (I suspect Yves Cornuiller will comment...)