Проблема группового изоморфизма
В абстрактной алгебре проблема группового изоморфизма — это проблема определения того, относятся ли два заданных представления конечных групп к изоморфным группам .
Проблема изоморфизма была сформулирована Максом Деном . [ 1 ] и вместе с проблемой слов и проблемой сопряженности является одной из трех фундаментальных проблем принятия решений в теории групп, которые он определил в 1911 году. [ 2 ] Все три проблемы неразрешимы : не существует компьютерного алгоритма, который правильно решает каждый случай проблемы изоморфизма или двух других проблем, независимо от того, сколько времени отведено на выполнение алгоритма. На самом деле проблема определения тривиальности группы неразрешима. [ 3 ] следствие теоремы Адяна-Рабина, принадлежащей Сергею Адяну и Майклу О. Рабину .
Проблема изоморфизма групп, в которой группы задаются таблицами умножения, может быть сведена к проблеме изоморфизма графов , но не наоборот. [ 4 ] Оба имеют алгоритмы с квазиполиномиальным временем , первый из которых с 1978 года приписывают Роберту Тарьяну. [ 5 ] а последний с 2015 года — Ласло Бабай . [ 6 ] Небольшое, но важное улучшение для случая p-групп класса 2 было получено в 2023 году Сяоруи Сунь. [ 7 ] [ 4 ]
Ссылки
[ редактировать ]- ^ Ден, Макс (1911). «О бесконечных разрывных группах». Математика Энн. 71 : 116–144. дои : 10.1007/BF01456932 . S2CID 123478582 .
- ^ Магнус, Вильгельм ; Каррасс, Абрахам и Солитар, Дональд (1996). Комбинаторная теория групп: представление групп с точки зрения генераторов и отношений (2-е изд.). Нью-Йорк: Dover Publications . стр. 24–29. ISBN 0486632814 . Проверено 14 октября 2022 г. - через VDOC.PUB.
- ^ Миллер, Чарльз Ф. III (1992). «Проблемы принятия решений для групп — обзор и размышления» (PDF) . В Баумслаге, Гилберт; Миллер, CF III (ред.). Алгоритмы и классификация в комбинаторной теории групп . Публикации НИИ математических наук. Том. 23. Нью-Йорк: Спрингер-Верлаг. стр. 1–59. дои : 10.1007/978-1-4613-9730-4_1 . ISBN 9781461397328 . (См. следствие 3.4)
- ^ Jump up to: а б Хартнетт, Кевин (23 июня 2023 г.). «Учёные-компьютерщики на шаг ближе к главной алгоритмической цели» . Журнал Кванта .
- ^ Миллер, Гэри Л. (1978). «На н войти в систему техника изоморфизма (Предварительный отчет)» . Труды десятого ежегодного симпозиума ACM по теории вычислений - STOC '78 . ACM Press. С. 51–58. doi : 10.1145/800133.804331 . ISBN 978-1-4503-7437-8 .
- ^ Бабай, Ласло (9 января 2017 г.), Обновление изоморфизма графов
- ^ Сунь, Сяоруй (2023). «Быстрый изоморфизм для p -групп класса 2 и экспоненты p ». arXiv : 2303.15412 [ cs.DS ].
- Джонсон, Д.Л. (1997). Презентации групп (2-е изд.). Кембридж: Издательство Кембриджского университета . п. 49. дои : 10.1017/CBO9781139168410 . ISBN 0521372038 .
 | Эта абстрактной алгебре статья, посвященная , незавершена . Вы можете помочь Википедии, расширив ее . |
 | Эта статья об математики незавершена . истории Вы можете помочь Википедии, расширив ее . |