Are there finitely generated groups whose word problem is solvable, but not quickly? It would be great to have specific examples, but existence results would also be helpful. 


All of the groups that I know with solvable word problem (linear groups, hyperbolic groups, branch groups) have a low-degree polynomial time algorithm for solving the problem. I am looking for something between those groups and the ones with unsolvable word problem. 



Groups where word problem is solvable, but not quickly?
There is a very nice recent paper "[Algorithmically complex residually finite groups](http://arxiv.org/abs/1204.6506)" 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.


