Groups, Geometry, and Dynamics
Full-Text PDF (303 KB) | Table of Contents | GGD summary
The conjugacy problem in the Grigorchuk group is polynomial time decidableIgor Lysenok, Alexei Myasnikov and Alexander Ushakov (1) Department of Mathematical Logic, Steklov Mathematical Institute, ul. Gubkina 8, 119991, MOSCOW, RUSSIAN FEDERATION
(2) Department of Mathematics and Statistics, McGill University, 845 Sherbrooke St. W., Quebec H3A 2T5, MONTREAL, CANADA
(3) Department of Mathematical Sciences, Stevens Institute of Technology, 1 Castle Point on Hudson, NJ 07030, HOBOKEN, UNITED STATES
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