Polynomial-time normalizers
Eugene M Luks, Takunari Miyazaki
Abstract
For an integer constant d > 0, let
Γd denote the class of finite groups all
of whose nonabelian composition factors lie in
Sd; in particular,
Γd includes all solvable groups.
Motivated by applications to graph-isomorphism testing, there has been
extensive study of the complexity of computation for permutation
groups in this class. In particular, the problems of finding set
stabilizers, intersections and centralizers have all been shown to be
polynomial-time computable. A notable open issue for the class
Γd has been the question of whether
normalizers can be found in polynomial time. We resolve this question
in the affirmative. We prove that, given permutation groups G, H
≤ Sym(Ω) such that G
∈Γd, the normalizer of H in
G can be found in polynomial time. Among other new
procedures, our method includes a key subroutine to solve the problem
of finding stabilizers of subspaces in linear representations of
permutation groups in Γd.
Full Text: PDF PostScript