Группа «черный ящик»
| Алгебраическая структура → Теория групп Теория групп |
|---|
 |
В теории вычислительных групп группа черного ящика ( группа черного ящика ) — это группа G , элементы которой кодируются битовыми строками длины N , а групповые операции выполняются оракулом ( « черный ящик »). Эти операции включают в себя:
- взяв произведение g · h элементов g и h ,
- взяв обратную g −1 элемента g ,
- решая, является ли g = 1.
Этот класс определен так, чтобы включать в себя как группы перестановок, так и группы матриц . Верхняя граница порядка G , определяемая формулой | г | ≤ 2 Н показывает, G конечна что .
Приложения
[ редактировать ]Группы «черных ящиков» были введены Бабаем и Семереди в 1984 году. [1] Они использовались в качестве формализма для (конструктивного) распознавания групп и проверки свойств . Известные алгоритмы включают алгоритм Бабая для поиска случайных элементов группы, [2] алгоритм замены продукта , [3] и проверка групповой коммутативности . [4]
Многие ранние алгоритмы CGT, такие как алгоритм Шрайера-Симса , требуют перестановками представления группы и, следовательно, не являются черным ящиком. Многие другие алгоритмы требуют нахождения порядка элементов . Поскольку существуют эффективные способы определения порядка элемента в группе перестановок или в группе матриц (метод для последнего описан Селлером и Лидхэм-Грин в 1997 году), обычно приходится предполагать, что группа черного ящика оснащен дополнительным оракулом для определения порядка элементов. [5]
См. также
[ редактировать ]Примечания
[ редактировать ]- ^ Бабай, Л.; Семереди, Э. (1984). «О сложности матричных групповых задач I». 25-й ежегодный симпозиум по основам информатики, 1984 г. стр. 229–240. дои : 10.1109/SFCS.1984.715919 . ISBN 0-8186-0591-Х .
- ^ Л. Бабай, Локальное разложение вершинно-транзитивных графов и случайная генерация в конечных группах , Тр. 23-й СТОК (1991), 164–174.
- ^ Фрэнк Селлер; Чарльз Р. Лидэм-Грин; Скотт Х. Мюррей; Элис К. Нимейер; Э.А. О'Брайен (1995). «Генерация случайных элементов конечной группы». Связь в алгебре . 23 (3): 4931–4948. CiteSeerX 10.1.1.43.2250 . дои : 10.1080/00927879508825509 .
- ^ Пак, Игорь (2012). «Проверка коммутативности группы и силы рандомизации» . LMS Журнал вычислений и математики . 15 : 38–43. дои : 10.1112/S1461157012000046 .
- ^ См. Холт и др. (2005).
Ссылки
[ редактировать ]- Дерек Ф. Холт, Беттина Эйк, Имонн А. О'Брайен, Справочник по вычислительной теории групп , Дискретная математика и ее приложения (Бока-Ратон). Чепмен и Холл/CRC, Бока-Ратон, Флорида, 2005 г. ISBN 1-58488-372-3
- Акос Сересс, Алгоритмы группы перестановок , Cambridge Tracts in Mathematics, vol. 152, Издательство Кембриджского университета, Кембридж, 2003. ISBN 0-521-66103-X .
- Кантор, Уильям М .; Сересс, Акос (2001). Классические группы «черного ящика» . Мемуары Американского математического общества. Том. 708. Американское математическое общество . ISBN 978-0-8218-2619-5 . ISSN 0065-9266 .