The conjugacy problem in the Grigorchuk group is polynomial time decidable
Igor LysenokSteklov Mathematical Institute, Moscow, Russian Federation
Alexei MyasnikovMcGill University, Montreal, Canada
Alexander UshakovStevens Institute of Technology, Hoboken, USA
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