¿Dado un grupo finito $G$, cuán eficiente puede uno hacer un algoritmo para encontrar el tamaño del más pequeño conjunto de $S$ tal que $G$ es isomorfo a un grupo de permutaciones de los miembros de $S$? ¿Y cambia la respuesta si uno requiere la salida para especificar no sólo la cardinalidad de $S$ pero la acción particular de $G$ $S$? ¿Podría tratarse de un problema NP-hard? ¿O es una cosa trivial cuya solución es conocida por todos en la tierra excepto yo? ¿O en algún lugar en el medio?
Respuesta
¿Demasiados anuncios?
Ver esta respuesta MO enlaces a varios documentos importantes.
La cita principal es: Johnson, L. D. "permutación mínimas representaciones de grupos finitos". Amer. J. matemáticas. 93 (1971), 857-866.
Edición (30/10/13): Compruebe el comentario a continuación de un libro completo sobre este tema.
