The conjugacy problem in the Grigorchuk group is polynomial time decidable

Igor Lysenok; Alexei Myasnikov; Alexander Ushakov

doi:10.4171/GGD/108

The conjugacy problem in the Grigorchuk group is polynomial time decidable

Department of Mathematical Sciences

RAS - Steklov Mathematical Institute

Research output: Contribution to journal › Article › peer-review

7 Scopus citations

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.

Original language	English
Pages (from-to)	813-833
Number of pages	21
Journal	Groups, Geometry, and Dynamics
Volume	4
Issue number	4
DOIs	https://doi.org/10.4171/GGD/108
State	Published - 2010

Keywords

Conjugacy problem
Grigorchuk group

Access to Document

10.4171/GGD/108

Cite this

@article{ced82534522e4dd5bea22215a74fbf66,

title = "The conjugacy problem in the Grigorchuk group is polynomial time decidable",

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.",

keywords = "Conjugacy problem, Grigorchuk group",

author = "Igor Lysenok and Alexei Myasnikov and Alexander Ushakov",

year = "2010",

doi = "10.4171/GGD/108",

language = "English",

volume = "4",

pages = "813--833",

number = "4",

}

TY - JOUR

T1 - The conjugacy problem in the Grigorchuk group is polynomial time decidable

AU - Lysenok, Igor

AU - Myasnikov, Alexei

AU - Ushakov, Alexander

PY - 2010

Y1 - 2010

N2 - 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.

AB - 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.

KW - Conjugacy problem

KW - Grigorchuk group

UR - https://www.scopus.com/pages/publications/78049490863

UR - https://www.scopus.com/pages/publications/78049490863#tab=citedBy

U2 - 10.4171/GGD/108

DO - 10.4171/GGD/108

M3 - Article

AN - SCOPUS:78049490863

SN - 1661-7207

VL - 4

SP - 813

EP - 833

JO - Groups, Geometry, and Dynamics

JF - Groups, Geometry, and Dynamics

IS - 4

ER -

The conjugacy problem in the Grigorchuk group is polynomial time decidable

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this