Skupina černé skříňky - Black box group - Wikipedia

Algebraická struktura → Skupinová teorie
Skupinová teorie
Cyklická skupina.svg

v teorie výpočetních grup, a skupina černé skříňky (skupina černé skříňky) je skupina G jejichž prvky jsou kódovány bitové řetězce délky Na skupinové operace provádí věštec („Černá skříňka "). Mezi tyto operace patří:

• užívání produktu G·h prvků G a h,
• přičemž inverzní G−1 prvku G,
• rozhodování, zda G = 1.

Tato třída je definována tak, aby zahrnovala obě permutační skupiny a maticové skupiny. Horní mez na objednat z G dané |G| ≤ 2N ukázat to G je konečný.

Aplikace

Skupiny černé skříňky představil Babai a Szemerédi v roce 1984.[1] Byly použity jako formalismus pro (konstruktivní) skupinové rozpoznávání a testování vlastností. Pozoruhodné algoritmy zahrnují Babaiho algoritmus pro hledání prvků náhodné skupiny,[2] the Algoritmus náhrady produktu,[3] a komutativita testovací skupiny.[4]

Mnoho raných algoritmů v CGT, například Algoritmus Schreier – Sims, vyžadují a permutační reprezentace skupiny a nejsou tedy černou skříní. Mnoho dalších algoritmů vyžaduje hledání objednávky prvků. Jelikož existují účinné způsoby, jak najít pořadí prvku ve permutační skupině nebo ve skupině matic (způsob pro tuto skupinu popisuje Celler a Leedham-Green v roce 1997) je běžným východiskem předpokládat, že skupina černé skříňky je vybavena dalším věštcem pro určování příkazů prvků.[5]

Viz také

Poznámky

  1. ^ Babai, L .; Szemeredi, E. (1984). „O složitosti problémů maticových skupin I“. 25. výroční sympozium o základech informatiky, 1984.: 229–240. doi:10.1109 / SFCS.1984.715919. ISBN  0-8186-0591-X.
  2. ^ L. Babai, Lokální expanze vertex-tranzitivních grafů a náhodné generování v konečných skupinách, Proc. 23. STOC (1991), 164–174.
  3. ^ Frank Celler; Charles R. Leedham-Green; Scott H. Murray; Alice C. Niemeyer; E.A. O'Brien (1995). Msgstr "Generování náhodných prvků konečné skupiny". Komunikace v algebře. 23 (3): 4931–4948. CiteSeerX  10.1.1.43.2250. doi:10.1080/00927879508825509.
  4. ^ Pak, Igor (2012). "Testování komutativity skupiny a síly náhodnosti". LMS Journal of Computation and Mathematics. 15: 38–43. doi:10.1112 / S1461157012000046.
  5. ^ Viz Hоlt et al. (2005).

Reference

  • Derek F. Holt, Bettina Eick, Eamonn A. O'Brien, Příručka teorie výpočetních grup, Diskrétní matematika a její aplikace (Boca Raton). Chapman & Hall / CRC, Boca Raton, Florida, 2005. ISBN  1-58488-372-3
  • Ákos Seress, Algoritmy permutačních skupin, Cambridge Tracts in Mathematics, roč. 152, Cambridge University Press, Cambridge, 2003. ISBN  0-521-66103-X.
  • Kantor, William M.; Seress, Ákos (2001). Black Box Classical Groups. Monografie Americké matematické společnosti. 708. Americká matematická společnost. ISBN  978-0-8218-2619-5. ISSN  0065-9266.