Группа черного ящика - Black box group

Алгебраическая структура → Теория групп
Теория групп
Циклическая группа.svg

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

• принимая продукт грамм·час элементов грамм и час,
• принимая обратное грамм−1 элемента грамм,
• решая, стоит ли грамм = 1.

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

Приложения

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

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

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

Примечания

  1. ^ Бабай, Л .; Семереди, Э. (1984). «О сложности матричных групповых задач I». 25-й ежегодный симпозиум по основам компьютерных наук, 1984.: 229–240. Дои:10.1109 / SFCS.1984.715919. ISBN  0-8186-0591-X.
  2. ^ Л. Бабай, Локальное расширение вершинно-транзитивных графов и случайная генерация в конечные группы, Proc. 23-й STOC (1991), 164–174.
  3. ^ Фрэнк Селлер; Чарльз Р. Лидхэм-Грин; Скотт Х. Мюррей; Алиса К. Нимейер; E.A. О'Брайен (1995). «Генерация случайных элементов конечной группы». Коммуникации в алгебре. 23 (3): 4931–4948. CiteSeerX  10.1.1.43.2250. Дои:10.1080/00927879508825509.
  4. ^ Пак, Игорь (2012). «Проверка коммутативности группы и силы рандомизации». Журнал вычислений и математики LMS. 15: 38–43. Дои:10.1112 / S1461157012000046.
  5. ^ См. Hоlt et al. (2005).

Рекомендации

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