Проблема группового изоморфизма - Group isomorphism problem

В абстрактная алгебра, то проблема группового изоморфизма это проблема решения определения двух данных представления конечных групп подарок изоморфный группы.

Проблема изоморфизма была обозначена Макс Ден в 1911 г.^[1] как одна из трех фундаментальных проблем принятия решений в теории групп; два других являются проблема со словом и проблема сопряженности. Все три проблемы неразрешимый: не существует компьютерного алгоритма, который правильно решает каждый случай проблемы изоморфизма или двух других проблем, независимо от того, сколько времени разрешено для выполнения алгоритма. На самом деле проблема определения тривиальности группы неразрешима,^[2] следствие Теорема Адиана-Рабина из-за Сергей Адян и Майкл О. Рабин.

использованная литература

1. Ден 1911.
2. Миллер, Чарльз (1992). «Решение задач для групп - обзор и размышления». (PDF). Алгоритмы и классификация в комбинаторной теории групп. Алгоритмы и классификация в комбинаторной теории групп (Беркли, Калифорния, 1989). Следствие 3.4: Спрингер. С. 1–59.

• Магнус, Вильгельм; Авраам Каррасс; Дональд Солитэр (1976). Комбинаторная теория групп. Представления групп в терминах генераторов и отношений. Dover Publications. п. 24. ISBN  0-486-63281-4.
• Джонсон, Д. (1990). Презентации групп. Издательство Кембриджского университета. п. 49. ISBN  0-521-37203-8.
• Ден, Макс (1911). "Über unendliche diskontinuierliche Gruppen". Математика. Анна. 71: 116–144. Дои:10.1007 / BF01456932.