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

  • Alexei Myasnikov

    McGill University, Montreal, Canada

  • Alexander Ushakov

    Stevens Institute of Technology, Hoboken, USA
The conjugacy problem in the Grigorchuk group is polynomial time decidable cover
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