Linear time algorithm for the conjugacy problem in the first Grigorchuk group

Mitra Modi, Mathew Seedhom, Alexander Ushakov

Research output: Contribution to journalArticlepeer-review

2 Scopus citations

Abstract

We prove that the conjugacy problem in the first Grigorchuk group can be solved in linear time. Furthermore, the problem to decide if a list of elements w1, wk contains a pair of conjugate elements can be solved in linear time. We also show that a conjugator for a pair of conjugate element u,v can be found in polynomial time.

Original languageEnglish
Pages (from-to)789-806
Number of pages18
JournalInternational Journal of Algebra and Computation
Volume31
Issue number4
DOIs
StatePublished - Jun 2021

Keywords

  • Grigorchuk group
  • complexity
  • conjugacy problem
  • word problem

Fingerprint

Dive into the research topics of 'Linear time algorithm for the conjugacy problem in the first Grigorchuk group'. Together they form a unique fingerprint.

Cite this