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

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

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

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

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

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

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

Див. також

• Неявний граф^[en]

Примітки

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).

Література

• Derek F. Holt, Bettina Eick, Eamonn A. O'Brien, Handbook of computational group theory, Discrete Mathematics and its Applications (Boca Raton). Chapman & Hall/CRC, Boca Raton, Florida, 2005. ISBN 1-58488-372-3
• Ákos Seress, Permutation group algorithms, Cambridge Tracts in Mathematics, vol. 152, Cambridge University Press, Cambridge, 2003. ISBN 0-521-66103-X
• Kantor, William M.; Seress, Ákos (2001). Black Box Classical Groups. Memoirs of the American Mathematical Society. Т. 708. American Mathematical Society. ISBN 978-0-8218-2619-5. ISSN 0065-9266.