Efficient Isomorphism Testing for a Class of Group Extensions

Details Efficient Isomorphism Testing for a Class of Group Extensions Efficient Isomorphism Testing for a Class of Group Extensions

2008-12-12

arxiv.org/abs/0812.2298v1

Computer Science

Data Structures and Algorithms

17 pages, accepted to the STACS 2009 conference

Scientific paper

The group isomorphism problem asks whether two given groups are isomorphic or not. Whereas the case where both groups are abelian is well understood and can be solved efficiently, very little is known about the complexity of isomorphism testing for nonabelian groups. In this paper we study this problem for a class of groups corresponding to one of the simplest ways of constructing nonabelian groups from abelian groups: the groups that are extensions of an abelian group A by a cyclic group of order m. We present an efficient algorithm solving the group isomorphism problem for all the groups of this class such that the order of A is coprime with m. More precisely, our algorithm runs in time almost linear in the orders of the input groups and works in the general setting where the groups are given as black-boxes.

Affiliated with

Also associated with

No associations

Rating

Efficient Isomorphism Testing for a Class of Group Extensions 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 Efficient Isomorphism Testing for a Class of Group Extensions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient Isomorphism Testing for a Class of Group Extensions will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-609481