Black box group

Algebraic structure → Group theory
Group theory

Basic notions

* Subgroup
* Normal subgroup

* Quotient group
* (Semi-)direct product

Group homomorphisms

* kernel
* image
* direct sum

* wreath product
* simple
* finite

* infinite
* continuous
* multiplicative

* additive
* cyclic
* abelian
* dihedral

* nilpotent
* solvable

* List of group theory topics

Finite groups

|  Classification of finite simple groups

* cyclic
* alternating
* Lie type
* sporadic

* Lagrange's theorem

* Sylow theorems
* Hall's theorem

* p-group
* Elementary abelian group

* Frobenius group

* Schur multiplier

* Symmetric group Sn

* Klein four-group V
* Dihedral group Dn
* Quaternion group Q
* Dicyclic group Dicn

* Discrete groups
* Lattices

* Integers (Z)
* Free group

Modular groups

* PSL(2,Z)
* SL(2,Z)

* Arithmetic group
* Lattice
* Hyperbolic group

Topological and Lie groups

* Solenoid
* Circle

* General linear GL(n)

* Special linear SL(n)

* Orthogonal O(n)

* Euclidean E(n)

* Special orthogonal SO(n)

* Unitary U(n)

* Special unitary SU(n)

* Symplectic Sp(n)

* G2
* F4
* E6
* E7
* E8

* Lorentz
* Poincaré
* Conformal

* Diffeomorphism
* Loop

Infinite dimensional Lie group

* O(∞)
* SU(∞)
* Sp(∞)

Algebraic groups

* Linear algebraic group

* Reductive group

* Abelian variety

* Elliptic curve

* v
* t
* e

In computational group theory, a black box group (black-box group) is a group G whose elements are encoded by bit strings of length N, and group operations are performed by an oracle (the "black box"). These operations include:

* taking a product g·h of elements g and h,
* taking an inverse g−1 of element g,
* deciding whether g = 1.

This class is defined to include both the permutation groups and the matrix groups. The upper bound on the order of G given by |G| ≤ 2N shows that G is finite.

## Contents

* 1 Applications
* 2 See also
* 3 Notes
* 4 References

## Applications

The black box groups were introduced by Babai and Szemerédi in 1984.[1] They were used as a formalism for (constructive) group recognition and property testing. Notable algorithms include the Babai's algorithm for finding random group elements,[2] the Product Replacement Algorithm,[3] and testing group commutativity.[4]

Many early algorithms in CGT, such as the Schreier–Sims algorithm, require a permutation representation of a group and thus are not black box. Many other algorithms require finding element orders. Since there are efficient ways of finding the order of an element in a permutation group or in a matrix group (a method for the latter is described by Celler and Leedham-Green in 1997), a common recourse is to assume that the black box group is equipped with a further oracle for determining element orders.[5]

## See also

* Implicit graph
* Matroid oracle

## Notes

1. ↑ Babai, L.; Szemeredi, E. (1984). "On the Complexity of Matrix Group Problems I". 25th Annual Symposium on Foundations of Computer Science, 1984. pp. 229–240. doi:10.1109/SFCS.1984.715919. ISBN 0-8186-0591-X.
2. ↑ L. Babai, Local expansion of vertex-transitive graphs and random generation in finite groups, Proc. 23rd STOC (1991), 164–174.
3. ↑ 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. doi:10.1080/00927879508825509.
4. ↑ "Testing commutativity of a group and the power of randomization". LMS Journal of Computation and Mathematics 15: 38–43. 2012. doi:10.1112/S1461157012000046.
5. ↑ See Hоlt et al. (2005).

## References

* 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.

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Black box group. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Black_box_group&oldid=209003"
*[v]: View this template
*[t]: Discuss this template
*[e]: Edit this template