Група чорної скриньки

В обчислювальній теорії груп група чорної скриньки (група чорного ящика) — це група G, елементи якої закодовано бітовими рядками довжини N, а групові операції виконує оракулчорна скринька»). Ці операції включають:

  • обчислення добутку g·h елементів g і h,
  • обчислення оберненого значення g−1 елемента g,
  • з'ясування, чи g = 1.

Цей клас визначено так, що він включає як групи перестановок, так і групи матриць. Верхня межа порядку G задана, як |G| ≤ 2N показує, що G — скінченна.

Застосування

Групи чорної скриньки представили 1984 року Бабай і Семереді[1]. Їх використовували як формалізм для (конструктивного) розпізнавання груп і перевірки властивостей[en]. Відомі алгоритми включають алгоритм Бабая для пошуку елементів випадкової групи,[2] алгоритм заміни добутку[3] та перевірку комутативності групи[4].

Багато ранніх алгоритмів у обчислювальній теорії груп, наприклад алгоритм Шраєра — Сімса[en], вимагають представлення групи перестановкою і, отже, не є чорною скринькою. Багато інших алгоритмів потребують пошуку порядків елементів. Оскільки існують ефективні способи знайти порядок елемента в групі перестановок або в матричній групі (метод для останньої описали 1997 року Селлер і Лідгем-Ґрін[en]), загальним виходом є припущення, що група чорної скриньки оснащена додатковим оракулом для визначення порядку елементів[5].

Див. також

Примітки

  1. Babai, L.; Szemeredi, E. (1984). On the Complexity of Matrix Group Problems I. 25th Annual Symposium on Foundations of Computer Science, 1984. с. 229—240. doi:10.1109/SFCS.1984.715919. ISBN 0-8186-0591-X.
  2. L. Babai, Local expansion of vertex-transitive graphs and random generation in finite groups, Proc. 23rd STOC (1991), 164—174.
  3. Frank Celler; Charles R. Leedham-Green; Scott H. Murray; Alice C. Niemeyer; E.A. O'Brien (1995). Generating random elements of a finite group. Communications in Algebra. 23 (3): 4931—4948. CiteSeerX 10.1.1.43.2250. doi:10.1080/00927879508825509.
  4. Pak, Igor (2012). Testing commutativity of a group and the power of randomization. LMS Journal of Computation and Mathematics. 15: 38—43. doi:10.1112/S1461157012000046.
  5. See Holt et al. (2005).

Література