Problema di isomorfismo di gruppo - Group isomorphism problem
In algebra astratta , il problema isomorfismo tra gruppi è il problema di decisione di determinare se due dati presentazioni di gruppo finiti presentano isomorfi gruppi .
Il problema dell'isomorfismo fu identificato da Max Dehn nel 1911 come uno dei tre problemi decisionali fondamentali nella teoria dei gruppi; gli altri due sono il problema della parola e il problema della coniugazione . Tutti e tre i problemi sono indecidibili : non esiste un algoritmo informatico che risolva correttamente ogni istanza del problema di isomorfismo, o degli altri due problemi, indipendentemente dal tempo concesso all'algoritmo per l'esecuzione. Infatti il problema di decidere se un gruppo è banale è indecidibile, conseguenza del teorema di Adian-Rabin dovuto a Sergei Adian e Michael O. Rabin .
Riferimenti
- Magno, Guglielmo ; Abramo Karrass; Donald Solitar (1976). Teoria combinatoria dei gruppi. Presentazioni di gruppi in termini di generatori e relazioni . Pubblicazioni di Dover . pag. 24. ISBN 0-486-63281-4.
- Johnson, DL (1990). Presentazioni di gruppi . Cambridge University Press . pag. 49. ISBN 0-521-37203-8.
- Dehn, Max (1911). "Uber unendliche diskontinuierliche Gruppen". Matematica. Anna. 71 : 116-144. doi : 10.1007/BF01456932 .
 |
Questa voce sull'algebra astratta è solo un abbozzo . Puoi aiutare Wikipedia espandendola . |
