Група чорної скриньки
В обчислювальній теорії груп група чорної скриньки (група чорного ящика) — це група 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].
Див. також
ред.Примітки
ред.- ↑ 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.
- ↑ L. Babai, Local expansion of vertex-transitive graphs and random generation in finite groups, Proc. 23rd STOC (1991), 164—174.
- ↑ 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.
- ↑ 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.
- ↑ 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.