> < ^ Date: Tue, 01 Oct 2002 13:35:21 -0400 (EDT)
< ^ From: Akos Seress <akos@math.ohio-state.edu >
< ^ Subject: Re: Complexity of group problem

Dear Forum Members,

Christopher Jefferson asked about the complexity of stabilizer chain
computations in permutation groups. Given G=<S> \le S_n,
generators for the point stabilizers (called a strong generating set)
can indeed be computed in polynomial time in |S| and n. The first
algorithm was given in

C. Sims: Computation with permutation groups, Proc. Second Symp. on
Symbolic and Algebraic Manipulation, ACM Press, 1971, pp. 23--28.

The first analysis that a version of Sims's algorithm runs in polynomial
time appeared in

M. Furst, J. Hopcroft, E. Luks: Polynomial-time algorithms for
permutation groups, Proc. 21st IEEE Symp. on Foundations of Computer
Science, IEEE Press, 1980, pp. 36--41.

The current asymptotically fastest strong generating set construction
is in

L. Babai, E. Luks, \'A. Seress: Fast management of permutation groups I,
SIAM J. Computing 26 (1997), 1310--1342. 

As a blatant self-advertisement, I'd like to mention that various strong
generating set constructions, and many more permutation group algorithms,
are described in my forthcoming book

\'A. Seress: Permutation Group Algorithms, Cambridge Univ. Press, 2002.

Best regards,
Akos Seress

> < [top]