Generic complexity of the Conjugacy Problem in HNN-extensions and algorithmic stratification of Miller's groups

Simple item page
dc.creatorBorovik, Alexandre V.
dc.creatorMyasnikov, Alexei G.
dc.creatorRemeslennikov, Vladimir N.
dc.date2009-03-22
dc.date.accessioned2026-07-07T12:55:36Z
dc.date.available2026-07-07T12:55:36Z
dc.descriptionWe 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 have be undecidable. Our results show that "hard" instances of the problem comprise a negligibly small part of the group.
dc.identifierhttps://arxiv.org/abs/0903.3754
dc.identifierhttp://arxiv.org/abs/0903.3754
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/224303
dc.subjectGroup Theory
dc.subject20F10 (Primary), 20P05 (Secondary)
dc.titleGeneric complexity of the Conjugacy Problem in HNN-extensions and algorithmic stratification of Miller's groups
dc.typetext

Files

Collections

arXiv