In this paper we prove that the conjugacy problem in the Grigorchuk group Γ has polynomial time complexity. This solves a problem posed by Grigorchuk rather unexpectedly.
Cite this article
Igor Lysenok, Alexei Myasnikov, Alexander Ushakov, The conjugacy problem in the Grigorchuk group is polynomial time decidable. Groups Geom. Dyn. 4 (2010), no. 4, pp. 813–833DOI 10.4171/GGD/108