В обчислювальній теорії груп група чорної скриньки (група чорного ящика) — це група G, елементи якої закодовано бітовими рядками довжини N, а групові операції виконує оракул («чорна скринька»). Ці операції включають:
обчислення добутку g·h елементів g і h, обчислення оберненого значення g−1 елемента g, з'ясування, чи g = 1.
Цей клас визначено так, що він включає як групи перестановок, так і групи матриць. Верхня межа порядку G задана, як |G| ≤ 2N показує, що G — скінченна.
Застосування Групи чорної скриньки представили 1984 року Бабай і Семереді. Їх використовували як формалізм для (конструктивного) розпізнавання груп і . Відомі алгоритми включають алгоритм Бабая для пошуку елементів випадкової групи,L. Babai, Local expansion of vertex-transitive graphs and random generation in finite groups, Proc. 23rd STOC (1991), 164—174. алгоритм заміни добутку та перевірку комутативності групи.
Багато ранніх алгоритмів у обчислювальній теорії груп, наприклад , вимагають представлення групи перестановкою і, отже, не є чорною скринькою. Багато інших алгоритмів потребують пошуку порядків елементів. Оскільки існують ефективні способи знайти порядок елемента в групі перестановок або в матричній групі (метод для останньої описали 1997 року Селлер і ), загальним виходом є припущення, що група чорної скриньки оснащена додатковим оракулом для визначення порядку елементів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. Ákos Seress, Permutation group algorithms, Cambridge Tracts in Mathematics, vol. 152, Cambridge University Press, Cambridge, 2003.