Re: Complexity of computing normal subgroup

mareg_at_mimosa.csv.warwick.ac.uk
Date: 12/31/03


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.