Black box group

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.

Applications

The black box groups were introduced by Babai and Szemerédi in 1984. 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,[1] the Product Replacement Algorithm,[2] and testing group commutativity.[3]

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.[4]

See also

Notes

  1. L. Babai, Local expansion of vertex-transitive graphs and random generation in finite groups, Proc. 23rd STOC (1991), 164–174.
  2. 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.
  3. 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.
  4. See Hоlt et al. (2005).

References

This article is issued from Wikipedia - version of the Tuesday, March 31, 2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.