arXiv Analytics

Sign in

arXiv:0903.3754 [math.GR]AbstractReferencesReviewsResources

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

Published 2009-03-22Version 1

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 have be undecidable. Our results show that "hard" instances of the problem comprise a negligibly small part of the group.

Categories: math.GR
Subjects: 20F10, 20P05
Related articles: Most relevant | Search more
arXiv:0903.3751 [math.GR] (Published 2009-03-22)
The Conjugacy Problem in Amalgamated Products I: Regular Elements and Black Holes
arXiv:2309.16613 [math.GR] (Published 2023-09-28)
Conjugacy in Rearrangement Groups of Fractals
arXiv:math/0402060 [math.GR] (Published 2004-02-04)
On the conjugacy problem for cyclic extensions of free groups

Links

Toolbox