Grupa czarnej skrzynki
|
Struktura algebraiczna → Teoria grup Teoria grup |
|---|
 |
|
Grupy modułowe
|
W obliczeniowej teorii grup grupa czarnych skrzynek ( grupa czarnych skrzynek ) to grupa G , której elementy są kodowane przez ciągi bitów o długości N , a operacje grupowe są wykonywane przez wyrocznię („ czarna skrzynka ”). Operacje te obejmują:
• biorąc iloczyn g · h elementów g i h , • biorąc odwrotność g −1 elementu g , • rozstrzygając, czy g = 1.
Ta klasa jest zdefiniowana tak, aby zawierała zarówno grupy permutacji , jak i grupy macierzowe . Górna granica rzędu G podana przez | G | ≤ 2 N pokazuje, że G jest skończony .
Aplikacje
Grupy czarnych skrzynek zostały wprowadzone przez Babai i Szemerédi w 1984 roku. Były używane jako formalizm do (konstruktywnego) rozpoznawania grup i testowania właściwości . Godne uwagi algorytmy obejmują algorytm Babai do znajdowania losowych elementów grupowych, algorytm zastępowania produktów i testowanie przemienności grup .
Wiele wczesnych algorytmów w CGT, takich jak algorytm Schreiera-Simsa , wymaga permutacyjnej reprezentacji grupy, a zatem nie jest czarną skrzynką. Wiele innych algorytmów wymaga znalezienia rzędów elementów . Ponieważ istnieją wydajne sposoby znajdowania kolejności elementu w grupie permutacji lub w grupie macierzowej (metodę dla tej ostatniej opisali Celler i Leedham-Green w 1997 r.), Powszechnym rozwiązaniem jest założenie, że grupa czarnych skrzynek jest wyposażony w dodatkową wyrocznię do określania rzędów elementów.
Zobacz też
Notatki
- Bibliografia _ Szemeredi, E. (1984). „O złożoności problemów grupy Matrix I”. 25. doroczne sympozjum na temat podstaw informatyki, 1984. : 229–240. doi : 10.1109/SFCS.1984.715919 . ISBN 0-8186-0591-X .
- ^ L. Babai, Lokalna ekspansja grafów przechodnich wierzchołków i generowanie losowe w skończonych grupach , Proc. 23. STOC (1991), 164–174.
- Bibliografia _ Charles R. Leedham-Green; Scotta H. Murraya; Alice C. Niemeyer; EA O'Brien (1995). „Generowanie losowych elementów skończonej grupy”. Komunikacja w algebrze . 23 (3): 4931–4948. CiteSeerX 10.1.1.43.2250 . doi : 10.1080/00927879508825509 .
- ^ Pak, Igor (2012). „Testowanie przemienności grupy i potęgi randomizacji” . LMS Journal of Computing and Mathematics . 15 : 38–43. doi : 10.1112/S1461157012000046 .
- ^ Patrz Hölt i in. (2005).
- Derek F. Holt, Bettina Eick, Eamonn A. O'Brien, Podręcznik obliczeniowej teorii grup , Matematyka dyskretna i jej zastosowania (Boca Raton). Chapman & Hall/CRC, Boca Raton, Floryda, 2005. ISBN 1-58488-372-3
- Ákos Seress, Algorytmy grup permutacji , Cambridge Tracts in Mathematics, tom. 152, Cambridge University Press, Cambridge, 2003. ISBN 0-521-66103-X .
- Kantor, William M .; Seress, Akos (2001). Klasyczne grupy czarnej skrzynki . Wspomnienia Amerykańskiego Towarzystwa Matematycznego. Tom. 708. Amerykańskie Towarzystwo Matematyczne . ISBN 978-0-8218-2619-5 . ISSN 0065-9266 .