Groep isomorfisme probleem - Group isomorphism problem
In abstracte algebra is het groepsisomorfismeprobleem het beslissingsprobleem om te bepalen of twee gegeven eindige groepspresentaties isomorfe groepen presenteren .
Het isomorfismeprobleem werd in 1911 door Max Dehn geïdentificeerd als een van de drie fundamentele beslissingsproblemen in de groepentheorie; de andere twee zijn het woordprobleem en het vervoegingsprobleem . Alle drie de problemen zijn onbeslisbaar : er bestaat geen computeralgoritme dat elk exemplaar van het isomorfismeprobleem, of van de andere twee problemen, correct oplost, ongeacht hoeveel tijd het algoritme laat lopen. In feite is het probleem om te beslissen of een groep triviaal is onbeslisbaar, een gevolg van de stelling van Adian-Rabin vanwege Sergei Adian en Michael O. Rabin .
Referenties
- Magnus, Wilhelm ; Abraham Karrass; Donald Solitaire (1976). Combinatorische groepentheorie. Presentaties van groepen in termen van generatoren en relaties . Dover-publicaties . blz. 24. ISBN 0-486-63281-4.
- Johnson, DL (1990). Presentaties van groepen . Cambridge University Press . blz. 49. ISBN 0-521-37203-8.
- Dehn, Max (1911). "Über unendliche diskontinuierliche Gruppen". Wiskunde. Ann. 71 : 116-144. doi : 10.1007/BF01456932 .
 |
Dit artikel over abstracte algebra is een stomp . Je kunt Wikipedia helpen door het uit te breiden . |
