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 indecidibles: 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 indecidible, 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 maquinas, como también decirnos que hacer con ellas.

Véase también: Teoría de la computabilidad

Los 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\leq _{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

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”​

Teoria de la complejidad computacional

Un 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, comunmente 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: $\forall x\in G,x\star y\in G$
• Asociatividad: $\forall x,y,z\in G,x\star (y\star z)=(x\star y)\star z$
• Identidad o existencia del elemento neutro: $\exists !e:\forall x\in G,x\star e=e\star x=x$
• Invertibilidad o simetría: $\forall x\in G$$\exists {\bar {x}}\in G:x\star {\overline {x}}={\overline {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\rightarrow H$ de modo tal que $\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\rightarrow H$ es un isomorfismo entre $S_{1}$ y $S_{2}$, donde $f$ se define por
   $f(n)={\begin{cases}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{cases}}$
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}mn^{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}nm^{m}+n^{2}nm^{2m})\subseteq O(n^{2}nm^{2m})\subseteq O(2^{2\log(n)+3})$ unidades de tiempo.

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 Adrian-Rabin ​ utilizando la teoria de la computación demuestra de manera más intuitiva el problema del isomorfismo de grupos.