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