El algoritmo de Schreier-Sims es un algoritmo basado en los estudios del matemático Otto Schreier y desarrollado por Charles Sims alrededor de los años 1970 y 1971.Este algoritmo busca encontrar una base, definida como una secuencia de puntos estabilizados, y un conjunto generador fuerte del grupo o SGS por sus siglas en inglés (Strong Generating Set), dado un conjunto generador.Debido a esto, el enfoque de fuerza bruta no es una opción a la hora de calcular el orden del grupopara, finalmente, obtener el SGS, es decir, una representación del grupo simétrico que permite computar eficientemente sobre este.[2] Hizo su postgrado en la Universidad de Harvard y recibió su Ph.D.Estudió en la Universidad de Vienna y obtuvo su doctorado en 1923.Schreier se trasladó después a la Universidad de Hamburgo.En 1928 se volvió profesor en la Universidad de Rostock.El algoritmo busca entregar conjuntos representativos de los co-sets, una base y un conjunto generador fuerte del grupo a representar, todo esto se define y explica a continuación:[6] Definición 1: Seaun grupo de permutación, se define su secuencia:un elemento del subgrupo, se define su co-set:Es posible observar que, por inducción, para un elementoEl algoritmo enfatiza en los grupos de permutación, sin embargo, el ejemplo anterior ejemplifica de forma sencilla lo que se busca.Aplicado el concepto para grupos de permutaciones, se calculan los subgrupos a partir de los elementos estabilizadores del grupo, para cierto punto afectado por la permutación.Esto es, las permutaciones que envíen dicho punto a sí mismo, dejándolo estable.Esto puede ser logrado definiendo cada subgrupo de la cadena como:, con respecto al grupo de permutación simétrico., tal que el estabilizador punto a punto de B es trivial (el único elemento que fija todos losPara mantener pequeño el tamaño de cada generador, y por ende el tamaño del generador fuerte final, se utiliza un filtro que sea un algoritmo para encontrar conjuntos generadores pequeños, usualmente el filtro de Sims o el filtro de Jerrum.[7] El algoritmo se aplica para cada subgrupo de la cadena, empezando enEl conjunto generador fuerte del grupo de permutaciones) La complejidad del algoritmo, ya sea tiempo de ejecución o memoria depende de la implementación que se use.[9] Estos algoritmos calculan una base y un conjunto generador (SGS) para el grupo en cuestión.Si denotamos los puntos elegidos del grupo para su análisis como, al aplicar el paso dos del algoritmo generamos un árbol de Schreier aplicando el método de Búsqueda a lo ancho (BFS).Al terminar la implementación el tamaño del grupo en cuestión va a estar dado por:En términos de memoria se debe tomar en cuenta que cada vez que se ejecuta el algoritmo para cada punto de, gracias al lema de Schreier, entonces para el peor caso (donde cada órbita sea todo el conjunto asociado al grupopasos para terminar), habría a lo sumoEntre los problemas en los que se utilizó el algoritmo de Schreier-Sims y posibles aplicaciones se encuentran: Entre las posibles aplicaciones están:
