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.



Relevant Pages

  • Re: Complexity of computing normal subgroup
    ... >>the testing of existence of a normal subgroup ... for a finite group input as a finite list of generators ... > of a subgroup of a symmetric group S_n, ... This of course includes the case of a finite group input by ...
    (comp.theory)
  • Re: Self Study problem help - Group theory
    ... We could exclude a finite number of these generators ... >will still construct all of Q, then we must remove a infinite ... >collection in order to attain a proper subgroup. ... >construct numbers with those prime powers in the denominator. ...
    (sci.math)
  • Re: Question on subgroups generated by conjugacy classes
    ... algebra book and could use some hints. ... only finitely many conjugates, then x and its conjugates generate a ... induced by the permutation it effects on the generators x1, ... Z] is isomorphic to a subgroup of the symmetric group on k ...
    (sci.math)
  • Re: Dense subgroup of R^n
    ... Suppose you have a discrete subgroup A of R^n. ... generators that has an accumulation point. ... of the fundamental domain, and so with norm less ...
    (sci.math)
  • Re: Self Study problem help - Group theory
    ... Seems to be a proper subgroup as well considering what I now know about ... denominator of the element that would generate the group. ... it seems that to get a set of generators for Q we'd ...
    (sci.math)