Re: Complexity of computing normal subgroup

From: Pinaki Mitra (pinaki_m_at_hotmail.com)
Date: 01/03/04


Date: 2 Jan 2004 23:10:07 -0800

mareg@mimosa.csv.warwick.ac.uk () wrote in message news:<bsu9b5$ipk$1@wisteria.csv.warwick.ac.uk>...
> 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.

If the group is finite then if I consider all possible subsets of the
group elements and test for the desired property we clearly have an
exponential time algorithm (though not polynomial) for the testing of
existence. That way the problem looks decidable. Any catch anywhere ?

Thanks.

--- Pinaki