Título: | Polynomial-Time Algorithms for Permutation Groups |
Autores: |
Furst, Merrick Hopcroft, John E. Luks, Eugene |
Fecha: |
2007-04-23 2007-04-23 1980-10 |
Publicador: | Cornell University |
Fuente: |
Ver documento Ver documento |
Tipo: | Technical Report |
Tema: |
computer science technical report |
Descripción: | A permutation group on n letters may always be represented by a small set of generators, even though its size may be exponential in n. We show that it is practical to use such a representation since many problems such as membership testing, equality testing, and inclusion testing are decidable in polynomial time. In addition, we demonstrate that the normal closure of a subgroup can be computed in polynomial time, and that this procedure can be used to test a group for solvability. We also describe an approach to computing the intersection of two groups. The procedures and techniques have wide applicability and have recently been used to improve many graph isomorphism algorithms. |
Idioma: | Inglés |
1 Dance in the Noh Theater, Volume 1: Dance Analysis por Bethe, Monica,Brazell, Karen | 6 Rationality and Reason Today por Welsch, Wolfgang |
2 Dance in the Noh Theater, Volume 3: Dance Patterns por Bethe, Monica,Brazell, Karen | 7 Reason: traditional and contemporary, or Why should we still speak of reason at all? por Welsch, Wolfgang |
3 Archives or Assets? por Hirtle, Peter B. | 8 High Precision Lattice QCD: Perturbations in a Non-Perturbative World por Mason, Quentin |
4 Digital Preservation and Copyright por Hirtle, Peter B. | 9 Unpublished Materials, New Technologies, and Copyright: Facilitating Scholarly Use por Hirtle, Peter B. |
5 Reason and Transition: On the Concept of Transversal Reason por Welsch, Wolfgang | 10 |