Groups, Geometry, and Dynamics

Full-Text PDF (303 KB) | Table of Contents | GGD summary
Volume 4, Issue 4, 2010, pp. 813–833
DOI: 10.4171/GGD/108

The conjugacy problem in the Grigorchuk group is polynomial time decidable

Igor Lysenok (1), Alexei Myasnikov (2) and Alexander Ushakov (3)

(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