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

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$