Problem izomorfizmu grupowego - Group isomorphism problem
W algebry abstrakcyjnej The Problem grupa izomorfizm jest problem decyzyjny określania, czy dwa podane prezentacje grup skończonych przedstawić izomorficzne grupy .
Problem izomorfizmu został zidentyfikowany przez Maxa Dehna w 1911 roku jako jeden z trzech podstawowych problemów decyzyjnych w teorii grup; pozostałe dwa to problem słów i problem koniugacji . Wszystkie trzy problemy są nierozstrzygalne : nie istnieje algorytm komputerowy, który poprawnie rozwiązuje każdy przypadek problemu izomorfizmu lub dwóch pozostałych problemów, niezależnie od tego, ile czasu zostało na jego działanie. W rzeczywistości problem z podjęciem decyzji, czy dana grupa jest trywialne jest nierozstrzygalny, konsekwencją twierdzenia Adian-Rabina powodu Siergiej Adian i Michael O. Rabin .
Bibliografia
- Magnus, Wilhelm ; Abraham Karrass; Donalda Solitara (1976). Kombinatoryczna teoria grup. Prezentacje grup w aspekcie generatorów i relacji . Publikacje Dover . str. 24. Numer ISBN 0-486-63281-4.
- Johnsona, DL (1990). Prezentacje grup . Wydawnictwo Uniwersytetu Cambridge . str. 49. Numer ISBN 0-521-37203-8.
- Dehn, Max (1911). „Uber unendliche diskontinuierliche Grouppen”. Matematyka. Anny. 71 : 116–144. doi : 10.1007/BF01456932 .
 |
Ten artykuł dotyczący algebry abstrakcyjnej jest skrótem . Możesz pomóc Wikipedii, rozwijając ją . |
