En teoría de grupos computacionales , un grupo de caja negra ( black-box group ) es un grupo G cuyos elementos están codificados por cadenas de bits de longitud N , y las operaciones de grupo las realiza un oráculo (la " caja negra "). Estas operaciones incluyen:
- tomando un producto g · h de los elementos g y h ,
- tomando una inversa g −1 del elemento g ,
- decidir si g = 1.
Esta clase se define para incluir tanto los grupos de permutación como los grupos de matrices . El límite superior del orden de G dado por | G | ≤ 2 N muestra que G es finito .
Aplicaciones
Los grupos de caja negra fueron introducidos por Babai y Szemerédi en 1984. [1] Se utilizaron como formalismo para el reconocimiento de grupos (constructivo) y la prueba de propiedades . Los algoritmos notables incluyen el algoritmo de Babai para encontrar elementos aleatorios de grupos, [2] el algoritmo de reemplazo de productos , [3] y la prueba de conmutatividad de grupos . [4]
Muchos de los primeros algoritmos de la CGT, como el algoritmo Schreier–Sims , requieren una representación de permutación de un grupo y, por lo tanto, no son de caja negra. Muchos otros algoritmos requieren encontrar el orden de los elementos . Dado que existen formas eficientes de encontrar el orden de un elemento en un grupo de permutación o en un grupo de matrices (Celler y Leedham-Green describen un método para este último en 1997), un recurso común es suponer que el grupo de caja negra está equipado con un oráculo adicional para determinar el orden de los elementos. [5]
Véase también
Notas
- ^ Babai, L.; Szemeredi, E. (1984). "Sobre la complejidad de los problemas de grupos de matrices I". 25.º Simposio anual sobre fundamentos de la informática, 1984. págs. 229-240. doi :10.1109/SFCS.1984.715919. ISBN 0-8186-0591-X.
- ^ L. Babai, Expansión local de gráficos transitivos de vértice y generación aleatoria en grupos finitos, Proc. 23rd STOC (1991), 164–174.
- ^ Frank Celler; Charles R. Leedham-Green; Scott H. Murray; Alicia C. Niemeyer; EA O'Brien (1995). "Generar elementos aleatorios de un grupo finito". Comunicaciones en Álgebra . 23 (3): 4931–4948. CiteSeerX 10.1.1.43.2250 . doi :10.1080/00927879508825509.
- ^ Pak, Igor (2012). "Prueba de conmutatividad de un grupo y el poder de la aleatorización". LMS Journal of Computation and Mathematics . 15 : 38–43. doi : 10.1112/S1461157012000046 .
- ^ Véase Holt et al. (2005).
Referencias
- Derek F. Holt, Bettina Eick, Eamonn A. O'Brien, Manual de teoría de grupos computacionales , Matemáticas discretas y sus aplicaciones (Boca Raton). Chapman & Hall/CRC, Boca Raton, Florida, 2005. ISBN 1-58488-372-3
- Ákos Seress, Algoritmos de grupos de permutación , Cambridge Tracts in Mathematics, vol. 152, Cambridge University Press, Cambridge, 2003. ISBN 0-521-66103-X .
- Kantor, William M. ; Seress, Ákos (2001). Grupos clásicos de caja negra . Memorias de la American Mathematical Society. Vol. 708. American Mathematical Society . ISBN 978-0-8218-2619-5. ISSN 0065-9266.
