Groups, Geometry, and Dynamics
Full-Text PDF (303 KB) | Metadata | Table of Contents | GGD summary
The conjugacy problem in the Grigorchuk group is polynomial time decidableIgor Lysenok, Alexei Myasnikov and Alexander Ushakov (1) Steklov Mathematical Institute, Moscow, Russian Federation
(2) McGill University, Montreal, Canada
(3) Stevens 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.
Keywords: Conjugacy problem, Grigorchuk group
Lysenok Igor, Myasnikov Alexei, Ushakov Alexander: The conjugacy problem in the Grigorchuk group is polynomial time decidable. Groups Geom. Dyn. 4 (2010), 813-833. doi: 10.4171/GGD/108