Según la wikipedia el problema de isomorfismo de grupo es un problema indecidible .
Cuando restringimos a grupos abelianos (contables), ¿se vuelve decidible o sigue siendo indecidible?
En caso de que sea decidible me encantaría tener una referencia a un algoritmo que lo decida.
Si se considera la noción de decidibilidad en el sentido de la decidibilidad de Turing, como es habitual en la teoría de la computabilidad, entonces no tiene sentido inmediato preguntar si el problema de isomorfismo para grupos arbitrarios contables es decidible o no, ya que la "entrada" para una instancia de este problema consistiría en dos objetos infinitos, los grupos en alguna forma de presentación. Esto nos lleva fuera del contexto de la decidibilidad con las máquinas de Turing, que trabajan con una entrada y una salida finitas.
El problema sí tiene sentido para los grupos finitamente presentados, ya que aquí se pueden dar dos de estas presentaciones. En el caso abeliano, el problema del isomorfismo en este caso es decidible. En el caso no abeliano, no es decidible -un resultado que se deriva de la no decidibilidad del problema de la palabra, ya que ni siquiera se puede determinar el caso especial de si una presentación dada es una presentación del grupo trivial.
Si se consideran grupos presentados computacionalmente, tomando como entradas dos programas que enumerarán las relaciones, entonces no se podrá decidir en tiempo finito ninguna propiedad no trivial de los conjuntos que enumeran. Esto es una consecuencia del teorema de Rice. Por ejemplo, no podrá decidir si los programas no enumerarán ninguna relación o todas las relaciones, por lo que el problema del isomorfismo no será decidible en este contexto.
Sin embargo, adoptando una perspectiva más teórica de conjuntos que computacional, se podría preguntar cuál es la complejidad teórica de conjuntos descriptiva del conjunto de pares de grupos abelianos contables isomorfos. Está claro que tiene una complejidad como máximo de $\Sigma^1_1$ es decir, analítica de cara a la luz, ya que dos grupos son isomorfos si existe un isomorfismo, y creo que es probable $\Sigma^1_1$ -completa, ya que los grupos abelianos contables pueden codificar bastante información, pero tendría que comprobarlo con mis colegas de teoría de conjuntos descriptiva.
También está el tema de la teoría de las relaciones de equivalencia de Borel, que considera la complejidad de las relaciones de equivalencia bajo la reducibilidad de Borel, y en general, la relación de isomorfismo para los grupos generados finitamente (no necesariamente abelianos) es una relación de Borel en el espacio relevante, pero bastante compleja. La relación de isomorfismo de los grupos contables arbitrarios es mucho más alta aún, y como he dicho, creo que sigue siendo alta incluso sólo para los grupos abelianos contables.
Esta no es una respuesta completa (de alguna manera no puedo comentar), pero cuando se habla de presentaciones de grupos abelianos sólo importan los exponentesvectores. Es decir: para una relación $x_1^{a_1}...x_n^{a_n}$ el único $[a_1,...,a_n]$ asuntos.
Por lo tanto, supongo que la cuestión se puede decidir creando una matriz en la que los exponentes-vectores sean sus filas (las entradas están en $\mathbb Z$ ) y llevarlo a alguna forma normal (triangular superior) utilizando el algoritmo euclidiano (nótese que $\mathbb Z$ no es un campo) lo que dará lugar al tipo de isomorfismo tal y como establece el teorema fundamental de los grupos abelianos.
No tengo una referencia sobre este conocimiento común, pero podría apuntar en alguna dirección.
actualización2: Acabo de notar que esto es exactamente lo que el Forma normal de Smith calcula. Pero esto sólo se aplica a las presentaciones finitas, como se indica en los comentarios.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
