En álgebra abstracta , el problema de isomorfismo de grupo es el problema de decisión de determinar si dos dados presentaciones de los grupos finitos presentan isomórficas grupos .
El problema del isomorfismo fue identificado por Max Dehn en 1911 [1] como uno de los tres problemas fundamentales de decisión en la teoría de grupos; los otros dos son el problema verbal y el problema de conjugación . Los tres problemas son indecidibles : no existe un algoritmo informático que resuelva correctamente todas las instancias del problema de isomorfismo, o de los otros dos problemas, independientemente de cuánto tiempo se permita para que se ejecute el algoritmo. De hecho, el problema de decidir si un grupo es trivial es indecidible, [2] una consecuencia del teorema de Adian-Rabin debido a Sergei Adian y Michael O. Rabin .
Referencias
- ^ Dehn 1911 .
- ^ Miller, Charles (1992). "Problemas de decisión para grupos: encuesta y reflexiones". (PDF) . Algoritmos y clasificación en teoría combinatoria de grupos . Algoritmos y clasificación en teoría combinatoria de grupos (Berkeley, CA, 1989). Corolario 3.4: Springer. págs. 1-59.Mantenimiento de CS1: ubicación ( enlace )
- Magnus, Wilhelm ; Abraham Karrass; Donald Solitar (1976). Teoría de grupos combinatoria. Presentaciones de grupos en cuanto a generadores y relaciones . Publicaciones de Dover . pag. 24. ISBN 0-486-63281-4.
- Johnson, DL (1990). Presentaciones de grupos . Prensa de la Universidad de Cambridge . pag. 49. ISBN 0-521-37203-8.
- Dehn, Max (1911). "Über unendliche diskontinuierliche Gruppen". Matemáticas. Ana. 71 : 116-144. doi : 10.1007 / BF01456932 .