Problema del isomorfismo de grupos

En álgebra abstracta, el problema de isomorfismo de grupo es el problema de decisión de determinar si dadas dos presentaciones de los grupos finitos presentan isomorfismo de grupos.

El problema de isomorfismo fue identificado por Max Dehn en 1911 como uno de los tres problemas de decisión fundamentales en la teoría de grupos; Los otros dos son el problema de palabra para grupos y el problema de la conjugación. Los tres problemas son insolubles: no existe un algoritmo informático que resuelva correctamente todas las instancias del problema de isomorfismo o de los otros dos problemas, independientemente del tiempo que se demore para que se ejecute el algoritmo. De hecho, el problema de decidir si un grupo es trivial es insoluble, una consecuencia del teorema de Adian-Rabin se debe a Sergei Adian (1955) e independientemente, Michael O. Rabin (1958).

Conceptos previos

Teoría de la computación

El formalismo que se desprende de esta teoría esta enmarcada en especial para las máquinas de Turing, estudia modelos abstractos para saber cómo se desempeñan en las máquinas, como también decirnos que hacer con ellas. Plantilla:VtLos problemas en la teoría de la computabilidad se clasifican de acuerdo a su grado de imposibilidad:

• Los computables son aquellos para los cuales sí existe un algoritmo que siempre los resuelve cuando hay una solución y además es capaz de distinguir los casos que no la tienen. También se les conoce como decidibles, resolubles o recursivos.
• Los semicomputables son aquellos para los cuales hay un algoritmo que es capaz de encontrar una solución si es que existe, pero ningún algoritmo que determine cuando la solución no existe (en cuyo caso el algoritmo para encontrar la solución entraría a un bucle infinito). El ejemplo clásico por excelencia es el problema de la parada. A estos problemas también se les conoce como listables, recursivamente enumerables o reconocibles, porque si se enlistan todos los casos posibles del problema, es posible reconocer a aquellos que sí tienen solución.
• Los incomputables son aquellos para los cuales no hay ningún algoritmo que los pueda resolver, no importando que tengan o no solución. El ejemplo clásico por excelencia es el problema de la implicación lógica, que consiste en determinar cuándo una proposición lógica es un teorema; para este problema no hay ningún algoritmo que en todos los casos pueda distinguir si una proposición o su negación es un teorema.

Hay una versión más general de esta clasificación, donde los problemas incomputables se subdividen a su vez en problemas más difíciles que otros. La herramienta principal para lograr estas clasificaciones es el concepto de reducibilidad: Un problema $A$ se reduce al problema $B$ si bajo la suposición de que se sabe resolver el problema $B$ es posible resolver al problema $A$; esto se denota por $A{\le }_{t}B$, e informalmente significa que el problema $A$ no es más difícil de resolver que el problema $B$. Por ejemplo, bajo la suposición de que una persona sabe sumar, es muy fácil enseñarle a multiplicar haciendo sumas repetidas, de manera que multiplicar se reduce a sumar.

Problemas de decisión

Para una serie de preguntas determina ’si’ o ’no’ al cumplir una o unas condiciones requeridas. Si determina ’si’ esto quiere decir que dicha pregunta pertenece al grupo.

Problemas de busquedad

Para solucionar un problema de búsqueda consiste en especificarun conjunto de soluciones (que puede ser conjunto vacío) para cada instancia del problema.

Tesis Church-Turing

Plantilla:AP La Tesis de Church-Turing se asume como cierta, pero no es un enunciado matemático susceptible de demostración dado que involucra la noción intuitiva de algoritmo. La evidencia de su verdad es abundante pero no definitiva.

Esta tesis ennuncia:

“Todo lo que es computable es Turing-Computable”

Teoría de la complejidad computacional

Plantilla:APUn problema se cataloga como "inherentemente difícil" si su solución requiere de una cantidad significativa de recursos computacionales, sin importar el algoritmo utilizado. La teoría de la complejidad computacional formaliza dicha aseveración, introduciendo modelos de computación matemáticos para el estudio de estos problemas y la cuantificación de la cantidad de recursos necesarios para resolverlos, comúnmente el tiempo de procesamiento y memoria.

Isomorfismo de grupos

Se dice que dos grupos son isomorfos si existe un homomorfismo de grupos biyectivo. Desde el punto de vista de la teoría de grupos, los grupos isomorfos tienen las mismas propiedades y sólo

se diferencian por los símbolos utilizados para denotar al conjunto, los elementos y la operación, por este motivo no es necesario distinguirlos entre sí.

Sean dos grupos finitos $S_1=(G,\star )$y $S_2=(H,\diamond )$para determinar si existe un isomorfismo ente $S_1$y $S_2$debemos  ver  que  la  operación  binaria $\star$ que  combina  dos elementos $G$ para asignarles un tercer elemento que también esta en $G$, para esto debe cumplir los axiomas de grupo:

• Clausura: $\mathrm{\forall }x\in G,x\star y\in G$
• Asociatividad: $\mathrm{\forall }x,y,z\in G,x\star (y\star z)=(x\star y)\star z$
• Identidad o existencia del elemento neutro: $\mathrm{\exists }!e:\mathrm{\forall }x\in G,x\star e=e\star x=x$
• Invertibilidad o simetría: $\mathrm{\forall }x\in G$$\mathrm{\exists }\overline{x}\in G:x\star \bar{x}=\bar{x}\star x=e$

El grupo

$S=(G,\star )$

tiene la propiedad de que cada uno de sus n-elementos admite un sistema

$X$

de como máximo

$m=\lfloor log(n)\rfloor$

generadores. Se dice que dos grupos

$S_1=(G,\star )$

y

$S_2=(H,\diamond )$

son isomorfos si existe una función biyectiva

$f:G\to H$

de modo tal que

$\mathrm{\forall }u,v\in G$

se tiene:

$f(u\star v)=f(u)\diamond f(v)$

y se notan como: $S_1\cong S_2$. Es posible obtener un sistema de generadores para un grupo $S=(G,\star )$ mediante la consideración de todas las posibles m-combinaciones de $G$ hasta que se halle una combinación tal que constituya un sistema de generadores para S (esto en tiempo sub-exponencial).

Algoritmo para determinar si dos grupos son isomorfos

1. Determinar un sistema de generadores para $S_1$
2. Asociar a cada elemento de $x\in G$ su representación $x=g_{i_1}\star g_{i_2}\star ...g_{i_h}$
3. Para cada m-permutación $z_1,z_2,...,z_m$ de $H$ evaluar si la función $f:G\to H$ es un isomorfismo entre $S_1$ y $S_2$, donde $f$ se define por
   $f(n)=\{\begin{array}{cc}{z}_i,& \text{Si }x\text{= }{g}_i\\ z_1\diamond z_2\text{...}\diamond z_m& \text{Si}x=g_{i_1}\star g_{i_2}\text{...}\star g_{i_h}\end{array}$
4. Si al menos existe una permutación para la cual $f$ es un isomorfismo, entonces se acepta, de lo contrario se rechaza.

Revisar si una

$m$

-combinación es un sistema de generadores toma

$O(n^{2}m!)$

pasos, entonces el procedimiento completo tomará

$O(n^{2}m{n}^m)$

. Además, verificar si la función

$f$

es un isomorfismo requiere

$O(n^{2}m)$

pasos, mientras el número de

$m$

-permutaciones esta acotado por 

$O(n^{2m})$

. De este modo el algoritmo requiere, al procesar un input de tamaño

$n$

$O(n^{2}n{m}^m+n^{2}n{m}^{2m})\subseteq O(n^{2}n{m}^{2m})\subseteq O(2^{2\log (n)+3})$

Del problema de isomorfismo de grupos se sabe que puede ser resuelto en espacio

$O({\log }^{2}n)$

y que puede ser reducido en tiempo polinomial al problema de isomorfismo de grafos. Dado que su dificultad es estrictamente menor que la exponencial, se desconoce su ubicación dentro de

$NP$

.

Problema del isomorfismo de grupos

Si el problema fundamental de las matemáticas es decidir cuando dos cosas son iguales, entonces el problema fundamental de la teoría de grupos es decidir cuando dos grupos son isomórficos. Basados en los resultados de Novikov y Andrey Markov Jr. sobre el problema de Homomorfismo de grupos es insoluble; el problema de isomorfismo de grupos fue demostrado por Sergei Adian (1955) e independientemente por Michael O. Rabin (1958) describiendo que este problema es insoluble. El teorema de Adian-Rabin utilizando la teoría de la computación demuestra de manera más intuitiva el problema del isomorfismo de grupos.

Propiedad de Markov

Una Propiedad de Markov P de grupos finitos presentables es una para el cual:

1. P es una propiedad abstracta, es decir, P se conserva bajo el isomorfismo de grupos.
2. Existen grupos finitos presentables $A_{+}$ con propiedad P.
3. Existen grupos finitos presentables $A_{-}$ no puede ser embebido como un subgrupo en ningún grupo finito presentable con la propiedad P.

Por ejemplo, sea un grupo finito con propiedad de Markov: Podemos tomar $A_{+}$ para ser un grupo trivial y podemos tomar $A_{-}$ para ser un grupo cíclico infinito $\mathbb{Z}$.

Teorema de Adian-Rabin

Sea P una propiedad de Markov de grupos finitos presentables. Entonces no existe un algoritmo que, dada una presentación finita $G=⟨X\mid R⟩$, decide si es o no un $G$definido por esta presentación con propiedad P.

Aquí la palabra algoritmo se utiliza en el sentido de la teoría de recursión. De forma más formal, la conclusión del teorema Adian–Rabin significa que el conjunto de todas las presentaciones finitas

$⟨x_1,x_2,x_3,\dots \mid R⟩$

(donde $x_1,x_2,x_3,\dots$ es un alfabeto contable finito fijo, y $R$ es un conjunto finito de relaciones en estos generadores y sus inversos) definiendo grupos con la propiedad P, no es un conjunto recursivo. El teorema de Adian-Rabin también implica que el complemento de una propiedad de Markov en la clase de grupos finamente presentables es algorítmicamente insoluble.

Idea de la demostración

La demostración en fuentes modernas a este problema se da desde la idea del algoritmo, implicando si un problema es decidible o no (tesis Church-Turing) "¿Puedo decidir si dos palabras en los generadores son iguales?" resulta una propiedad intrínseca del grupo, vinculado a las máquinas de Turing. Con esto se puede hablar del teorema Novikov-Boone donde un grupo finito de presentaciones de $G$ de manera tal que la palabra "problema" es indecidible, o dicho informalmente que existe el grupo $G$de tal manera que es imposible saber si un elemento es trivial o no. (nota: la palabra problema es soluble para grupos finitos). El problema de conjugación para grupos muestra que si dos elementos son decidibles si estos son conjugados, es decir si existe un tercer elemento que sea la inversa de digamos el primer elemento y unimos esta inversa con el primer elemento obtenemos el segundo elemento, esto nos da que el problema es insoluble, pero el problema de Collins indica que si existe un grupo de presentaciones finito $G$es soluble para la palabra problema, pero insoluble para el problema de conjugación (un punto intermedio). El teorema de Adian-Rabin como una conclusión dice que es insoluble si un número finito de presentaciones define el trival para finalmente decir que el problema de isomorfismo de grupos sean dos presentaciones, entonces podemos decir si se define un isomorfismo de grupos. En realidad el teorema Adian-Rabin es el resultado es más profundo, demuestran que "propiedades de Markov" de presentaciones finitas los grupos no son recursivamente reconocibles.

Discusión

Complejidad de problemas de isomorfismo

Si uno de los dos grupos sobre los que queremos determinar el isomorfismo se puede generar por $k$ elementos entonces el problema de isomorfismo puede ser decidido en tiempo $n^k+O(1)$, con n el orden del grupo. Como para todos los grupos el número máximo de generadores es log n (es decir $k\le \log n$), se obtiene la cota superior de $n^{\log n}+O(1)$. De esto se deduce que para los grupos 2-generables el problema de isomorfismo de grupos es polinomico. Ahora bien la complejidad de los problemas de isomorfismo dado por insoluble, subexponencial, Quasipolinomial, polinomial enmarcado al problema de isomorfismo de grafos sea reducible (polinómicamente equivalente) al problema de isomorfismo de grupos es un problema abierto. El problema de isomorfismo de grupos en representación normal (el input es la tabla de Cayley o tabla de multiplicación del grupo) es polinómicamente equivalente al problema de isomorfismo de grafos de Cayley. El problema de isomorfismo de grupos (representación normal) es también reducible (polinómicamente equivalente) al problema de isomorfismo de grafos generales (en representación normal). Este es un resultado de Miller y Monk de 1979, del que se tienen variaciones. Con el reciente resultado de Babai, es de destacar que los dos problemas (isomorfismo de grafos y de grupos) tienen una cota superior O(cuasipolinómica). Tenga en cuenta que hay un simple $n^{\log n}+O(1)$tiempo para isomorfismo de grupos, mientras que el algoritmo más conocido para isomorfismo de grafos toma tiempo $2(\log n{)}^c$ para algunos c ≥ 3 y es más complicado.