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

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

2009-03-22

arxiv.org/abs/0903.3754v1

Mathematics

Group Theory

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Generic complexity of the Conjugacy Problem in HNN-extensions and algorithmic stratification of Miller's groups does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Generic complexity of the Conjugacy Problem in HNN-extensions and algorithmic stratification of Miller's groups, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Generic complexity of the Conjugacy Problem in HNN-extensions and algorithmic stratification of Miller's groups will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-191077