Problema de decisión
En álgebra abstracta , el problema de isomorfismo de grupos es el problema de decisión de determinar si dos presentaciones de grupos finitos dadas se refieren a grupos isomorfos .
El problema del isomorfismo fue formulado por Max Dehn , [1] y junto con el problema de las palabras y el problema de la conjugación , es uno de los tres problemas de decisión fundamentales en la teoría de grupos que identificó en 1911. [2] Los tres problemas son indecidibles : no existe un algoritmo informático que resuelva correctamente cada instancia del problema del isomorfismo, o de los otros dos problemas, independientemente de cuánto tiempo se le permita al algoritmo ejecutarse. De hecho, el problema de decidir si un grupo es trivial es indecidible, [3] una consecuencia del teorema de Adian-Rabin debido a Sergei Adian y Michael O. Rabin .
El problema de isomorfismo de grupos, en el que los grupos están dados por tablas de multiplicar, se puede reducir a un problema de isomorfismo de grafos pero no al revés. [4] Ambos tienen algoritmos de tiempo cuasi-polinomial , el primero desde 1978 atribuido a Robert Tarjan [5] y el segundo desde 2015 por László Babai . [6] Una pequeña pero importante mejora para el caso de p-grupos de clase 2 fue obtenida en 2023 por Xiaorui Sun. [7] [4]
Referencias
- ^ Dehn, Max (1911). "Über unendliche diskontinuierliche Gruppenn". Matemáticas. Ana. 71 : 116-144. doi :10.1007/BF01456932. S2CID 123478582.
- ^ Magnus, Wilhelm ; Karrass, Abraham y Solitar, Donald (1996). Teoría combinatoria de grupos: presentaciones de grupos en términos de generadores y relaciones (2.ª ed.). Nueva York: Dover Publications . págs. 24–29. ISBN 0486632814. Recuperado el 14 de octubre de 2022 – vía VDOC.PUB.
- ^ Miller, Charles F. III (1992). "Problemas de decisión para grupos: estudio y reflexiones" (PDF) . En Baumslag, Gilbert; Miller, CF III (eds.). Algoritmos y clasificación en teoría combinatoria de grupos . Publicaciones del Instituto de Investigación de Ciencias Matemáticas. Vol. 23. Nueva York: Springer-Verlag. págs. 1–59. doi :10.1007/978-1-4613-9730-4_1. ISBN . 9781461397328.(Véase Corolario 3.4)
- ^ ab Hartnett, Kevin (23 de junio de 2023). "Los científicos informáticos se acercan cada vez más a un importante objetivo algorítmico". Revista Quanta .
- ^ Miller, Gary L. (1978). "Sobre la técnica del isomorfismo nlog n (informe preliminar)". Actas del décimo simposio anual de la ACM sobre teoría de la computación - STOC '78 . ACM Press. págs. 51–58. doi :10.1145/800133.804331. ISBN 978-1-4503-7437-8.
- ^ Babai, László (9 de enero de 2017), Actualización de isomorfismo gráfico
- ^ Sun, Xiaorui (2023). "Isomorfismo más rápido para p -grupos de clase 2 y exponente p ". arXiv : 2303.15412 [cs.DS].
