The conjugacy problem in the Grigorchuk group is polynomial time decidable

Igor Lysenok; Alexei Myasnikov; Alexander Ushakov

doi:10.4171/ggd/108

JournalsggdVol. 4, No. 4pp. 813–833

The conjugacy problem in the Grigorchuk group is polynomial time decidable

Igor Lysenok
Steklov Mathematical Institute, Moscow, Russian Federation
- MathSciNet
- zbMATH Open
Alexei Myasnikov
McGill University, Montreal, Canada
Alexander Ushakov
Stevens Institute of Technology, Hoboken, USA
- MathSciNet
- zbMATH Open

Download PDF

Abstract

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–833

DOI 10.4171/GGD/108