# Re: Complexity of computing normal subgroup

*mareg_at_mimosa.csv.warwick.ac.uk*

**Date:** 12/31/03

**Next message:**Michael N. Christoff: "Re: Complexity of computing normal subgroup"**Previous message:**Pinaki Mitra: "Complexity of computing normal subgroup"**In reply to:**Pinaki Mitra: "Complexity of computing normal subgroup"**Next in thread:**Michael N. Christoff: "Re: Complexity of computing normal subgroup"**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ]

Date: Wed, 31 Dec 2003 10:44:53 +0000 (UTC)

In article <l.1072860562.1869232177@[203.197.122.201]>,

u725372314@spawnkill.ip-mobilphone.net (Pinaki Mitra) writes:

*>What is the computational complexity of
*

*>the testing of existence of a normal subgroup
*

*>of a group besides the trivial one containing
*

*>the identity element. Is it polynomial or
*

*>NP-complete ?
*

This depends on how the group is input. For a group defined by a finite

presentation using generators and relations, I am virtually certain that

this problem is provably undecidable. Almost all of the most obvious

and natural questions that you can ask about such a group, like "is it

trivial?", are undecidable.

On the other hand, for a finite group input as a finite list of generators

of a subgroup of a symmetric group S_n, the problem is polynomial. Indeed,

generators of the subgroups in a composition series, and the isomorphism

types of the composition factors can be determined in polynomial time.

See, for example, the book "Permutation Group Algorithms" by Akos Seress,

CUP 2003. This of course includes the case of a finite group input by

multiplication table, but is much stronger than that.

Derek Holt.

**Next message:**Michael N. Christoff: "Re: Complexity of computing normal subgroup"**Previous message:**Pinaki Mitra: "Complexity of computing normal subgroup"**In reply to:**Pinaki Mitra: "Complexity of computing normal subgroup"**Next in thread:**Michael N. Christoff: "Re: Complexity of computing normal subgroup"**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ]