¿Existe un algoritmo de tiempo polinómico para decidir si dos permutaciones generan [matemáticas] S_n [/ matemáticas]?

Answer 1

Si ambas permutaciones son pares, generan un subgrupo de . De lo contrario, con una probabilidad cercana a 1 (como ) generarán (esto supone que se eligen uniformemente al azar). Otras comprobaciones sencillas: ¿dejan los dos generadores un elemento fijo fijo? ¿Ambas mueven al menos algún elemento fijo? (es decir, tener soporte no disjunto) Si un elemento es cualquier ciclo completo y el otro es cualquier transposición, entonces generan .

En general, es posible encontrar (en poli-tiempo) el tamaño del subgrupo generado por dos permutaciones, y compararlo con . Los paquetes de álgebra computacional (como GAP) implementan tales algoritmos.

Answer 2

Esto se llama prueba de membresía grupal . Denota por G el grupo generado por sus dos permutaciones y luego prueba si los generadores estándar, digamos transposición y un ciclo largo, se encuentran en G. La membresía del grupo se realiza a través de la construcción del llamado grupo electrógeno fuerte , introducido por primera vez por Charles Sims en 1970. Vea la página de Wikipedia y consulte el libro de Seress allí:
https://en.wikipedia.org/wiki/Sc …
https://en.wikipedia.org/wiki/St …

Cooperman y Finkelstein ofrecen una buena variación probabilística de este algoritmo que mejora el tiempo, y con una exposición muy elegante:
“Herramientas combinatorias para la teoría del grupo computacional” (1991)
http://www.ccs.neu.edu/home/gene …

Answer 3

Así es como lo haría:

• Si tiene un grupo generado por algunas permutaciones [math] g_1, \ dots, g_m [/ math] actuando sobre [math] \ {1, \ dots, n \} [/ math], puede calcular fácilmente si el grupo Es transitivo. Es solo un cálculo de componentes conectados y esto se realiza en tiempo polinómico.
• Si tiene un grupo de permutación [matemática] G [/ matemática] que actúa sobre [matemática] \ {1, \ puntos, n \} [/ matemática] generada por permutación, entonces puede calcular el estabilizador de un punto [matemática] 1 [/ matemáticas] relativamente eficiente. Tiempo polinómico, no estoy seguro, pero creo que sí. Luego obtendrá un grupo electrógeno para el estabilizador.
• Entonces, puedes iterar. No necesita iterar [matemáticas] n [/ matemáticas] veces (en cuyo caso no se garantizaría que el algoritmo sea polinómico). Solo necesita iterar [matemáticas] 6 [/ matemáticas] veces.
• La razón es que los grupos que son [matemáticos] k [/ matemáticos] transitivos para [matemáticos] k \ geq 2 [/ matemáticos] se clasifican (ver referencias en el grupo transitivo 2) y los únicos que son más de 5- transitivos son [matemática] S_n [/ matemática] y [matemática] A_n [/ matemática]. Decidir entre ambos es muy fácil.
• En la práctica, existen mejores algoritmos para probar este tipo de cosas y se implementan en paquetes de Álgebra de computadora como GAP o MAGMA. Para el Sistema GAP de código abierto para Álgebra Computacional Discreta, el archivo a buscar es gpprmsya.gi y la referencia dada allí es la Sección 10.2 de Algoritmos de Grupo de Permutación, Ákos Seress.