Generic complexity of the conjugacy problem in HNN-extensions and algorithmic stratification of Miller's groups

Alexandre V. Borovik, Alexei G. Myasnikov, Vladimir N. Remeslennikov

Research output: Contribution to journalArticlepeer-review

17 Scopus citations

Abstract

We discuss time complexity of the Conjugacy Problem in HNN-extensions of groups, in particular, in Miller's groups. We show that for "almost all", in some explicit sense, elements, the Conjugacy Problem is decidable in cubic time. It is worth noting that the Conjugacy Problem in a Miller group may be undecidable. Our results show that "hard" instances of the problem comprise a negligibly small part of the group.

Original languageEnglish
Pages (from-to)963-967
Number of pages5
JournalInternational Journal of Algebra and Computation
Volume17
Issue number5-6
DOIs
StatePublished - 2007

Keywords

  • Algorithm
  • Complexity
  • Conjugation
  • HNN-extension

Fingerprint

Dive into the research topics of 'Generic complexity of the conjugacy problem in HNN-extensions and algorithmic stratification of Miller's groups'. Together they form a unique fingerprint.

Cite this