Polynomial-time normalizers

Abstract : For an integer constant d \textgreater 0, let Gamma(d) denote the class of finite groups all of whose nonabelian composition factors lie in S-d; in particular, Gamma(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 Gamma(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 \textless= Sym(Omega) such that G is an element of Gamma(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 Gamma(d).
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2011, Vol. 13 no. 4 (4), pp.61--96
Liste complète des métadonnées

Littérature citée [43 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00990473
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : mardi 13 mai 2014 - 15:38:56
Dernière modification le : jeudi 7 septembre 2017 - 01:03:38
Document(s) archivé(s) le : lundi 10 avril 2017 - 22:24:52

Fichier

2058-6664-1-PB.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00990473, version 1

Collections

Citation

Eugene M. Luks, Takunari Miyazaki. Polynomial-time normalizers. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2011, Vol. 13 no. 4 (4), pp.61--96. 〈hal-00990473〉

Partager

Métriques

Consultations de la notice

67

Téléchargements de fichiers

215