Geodesic
The conjugacy problem in the Grigorchuk group is polynomial time decidable
Igor Lysenok1 ; Alexei Myasnikov2 orcid ; Alexander Ushakov3
1Steklov Mathematical Institute, Moscow, Russian Federation
2McGill University, Montreal, Canada
3Stevens Institute of Technology, Hoboken, USA
Groups, geometry, and dynamics, Tome 4 (2010) no. 4, pp. 813-833

Voir la notice de l'article provenant de la source EMS Press

DOI

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.
DOI : 10.4171/ggd/108
Classification : 20-XX, 00-XX
Mots-clés : Conjugacy problem, Grigorchuk group

Igor Lysenok  1   ; Alexei Myasnikov  2   ; Alexander Ushakov  3

1 Steklov Mathematical Institute, Moscow, Russian Federation
2 McGill University, Montreal, Canada
3 Stevens Institute of Technology, Hoboken, USA 
Igor Lysenok; Alexei Myasnikov; Alexander Ushakov. The conjugacy problem in the Grigorchuk group is polynomial time decidable. Groups, geometry, and dynamics, Tome 4 (2010) no. 4, pp. 813-833. doi: 10.4171/ggd/108
@article{10_4171_ggd_108,
     author = {Igor Lysenok and Alexei Myasnikov and Alexander Ushakov},
     title = {The conjugacy problem in the {Grigorchuk} group is polynomial time decidable},
     journal = {Groups, geometry, and dynamics},
     pages = {813--833},
     year = {2010},
     volume = {4},
     number = {4},
     doi = {10.4171/ggd/108},
     url = {http://geodesic.mathdoc.fr/articles/10.4171/ggd/108/}
}
TY  - JOUR
AU  - Igor Lysenok
AU  - Alexei Myasnikov
AU  - Alexander Ushakov
TI  - The conjugacy problem in the Grigorchuk group is polynomial time decidable
JO  - Groups, geometry, and dynamics
PY  - 2010
SP  - 813
EP  - 833
VL  - 4
IS  - 4
UR  - http://geodesic.mathdoc.fr/articles/10.4171/ggd/108/
DO  - 10.4171/ggd/108
ID  - 10_4171_ggd_108
ER  - 
%0 Journal Article
%A Igor Lysenok
%A Alexei Myasnikov
%A Alexander Ushakov
%T The conjugacy problem in the Grigorchuk group is polynomial time decidable
%J Groups, geometry, and dynamics
%D 2010
%P 813-833
%V 4
%N 4
%U http://geodesic.mathdoc.fr/articles/10.4171/ggd/108/
%R 10.4171/ggd/108
%F 10_4171_ggd_108

Cité par Sources :