Algoritmo de descomposición de permutaciones

Question

Existe un algoritmo para resolver el siguiente problema: supongamos $g_1,\ldots,g_n$ ser permutaciones en algunos de los (grandes) grupo simétrico, y $g$ ser una permutación que se sabe que es en el subgrupo generado por a $g_1,\ldots,g_n$, podemos escribir $g$ explícitamente como un producto de la $g_i$'s?

Mi motivación es que estoy TAing una intro álgebra abstracta curso, y me gustaría utilizar el cubo de Rubik para motivar a un montón de cosas para mis alumnos, y, en particular, mostramos un algoritmo para resolverlo utilizando la teoría de grupos. (Que es, me pueden escribir lo permutación de los cubos que tengo, y quiero descomponer en basic rotaciones, que luego de invertir y hacer en el orden inverso para volver al estado resuelto.) A pesar de que estoy interesado en el caso más general, no sólo para el Rubik(n) grupos, si la solución funciona.

Nota: realmente no sé qué palabras usar para resolver este problema, si alguien puede que me señale el derecho de los términos de búsqueda de google para obtener los resultados que estoy buscando, estaré encantado de cerrar este.

Answer 1

Ver este artículo:

http://www.dartmouth.edu/~rah/juegos-con-los algoritmos.pdf

Página 22 contiene un estudio del problema en el que está interesado. Al parecer, existe un polinomio tiempo algoritmo para verificar si existe una solución (también regresará algunos representa implícitamente la solución), pero encontrar la solución con el menor número de movimientos es, no es de extrañar, PSPACE-completo.

La referencia original es:

Marca Jerrum: La Complejidad de Encontrar el Mínimo de Longitud Generador de Secuencias. Teori. Comput. Sci. 36: 265-289 (1985)

Answer 2

Sí. La regla general es que los grupos descritos por las permutaciones son computacionalmente fácil, grupos descritos por generadores y relaciones tienen problemas computacionales que son generalmente indecidible, y la matriz de los grupos están en algún lugar entre.

Hay un libro entero "Permutación grupo de algoritmos" por Seress, Cambridge University Press, 2003.

La principal técnica para la permutación de grupos que se llama la Schreier–Sims algoritmo; hay una encuesta aquí, por ejemplo. La idea es estabilizar la permutan los elementos de una en una. Como el Mitch ya se dijo, sin embargo, esto no encontrar la más corta de la palabra en los generadores que produce un grupo determinado elemento, que es un problema más difícil.