Группа черного ящика

В теории вычислительных групп группа черного ящика ( группа черного ящика ) — это группа G , элементы которой кодируются битовыми строками длины N , а групповые операции выполняются оракулом ( « черным ящиком »). К таким операциям относятся:

• беря произведение g · h элементов g и h ,
• беря обратный g ⁻¹ элемента g ,
• решая, g  = 1.

Этот класс определяется как включающий как группы перестановок , так и матричные группы . Верхняя граница порядка G , заданная как | G | ≤ 2 ^N, показывает , что G конечна .

Приложения

Группы черного ящика были введены Бабаем и Семереди в 1984 году. ^[1] Они использовались в качестве формализма для (конструктивного) распознавания групп и проверки свойств . Известные алгоритмы включают алгоритм Бабая для поиска случайных элементов группы, ^[2] алгоритм замены продукта , ^[3] и проверку коммутативности групп . ^[4]

Многие ранние алгоритмы в CGT, такие как алгоритм Шрайера–Симса , требуют представления группы перестановками и, таким образом, не являются черным ящиком. Многие другие алгоритмы требуют нахождения порядков элементов . Поскольку существуют эффективные способы нахождения порядка элемента в группе перестановок или в матричной группе (метод для последнего описан Целлером и Лидхэм-Грином в 1997 году), распространенным выходом является предположение, что группа черных ящиков снабжена дополнительным оракулом для определения порядков элементов. ^[5]

Смотрите также

• Неявный граф
• Матроидный оракул

Примечания

1. Бабай, Л.; Семереди, Э. (1984). «О сложности матричных групповых задач I». 25-й ежегодный симпозиум по основам компьютерной науки, 1984. стр. 229–240. doi :10.1109/SFCS.1984.715919. ISBN 0-8186-0591-X.
2. Л. Бабай, Локальное расширение вершинно-транзитивных графов и случайная генерация в конечных группах, Труды 23-й конференции STOC (1991), 164–174.
3. Фрэнк Селлер; Чарльз Р. Лидхэм-Грин; Скотт Х. Мюррей; Элис К. Нимейер; EA O'Brien (1995). «Генерация случайных элементов конечной группы». Communications in Algebra . 23 (3): 4931–4948. CiteSeerX 10.1.1.43.2250 . doi :10.1080/00927879508825509. 
4. Пак, Игорь (2012). «Проверка коммутативности группы и мощности рандомизации». LMS Journal of Computation and Mathematics . 15 : 38–43. doi : 10.1112/S1461157012000046 .
5. См. Холт и др. (2005).

Ссылки

• Дерек Ф. Холт, Беттина Эйк, Имонн А. О'Брайен, Справочник по вычислительной теории групп , Дискретная математика и ее приложения (Бока-Ратон). Chapman & Hall/CRC, Бока-Ратон, Флорида, 2005. ISBN 1-58488-372-3 
• Акош Сереш, Алгоритмы групп перестановок , Cambridge Tracts in Mathematics, т. 152, Cambridge University Press, Кембридж, 2003. ISBN 0-521-66103-X . 
• Кантор, Уильям М.; Сересс, Акош (2001). Black Box Classical Groups . Мемуары Американского математического общества. Том 708. Американское математическое общество . ISBN 978-0-8218-2619-5. ISSN  0065-9266.