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.
01Applications
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, the Product Replacement Algorithm, and testing group commutativity.
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.
Sources and credits
This article is adapted from the Wikipedia article “Black box group”, written by its contributors and licensed under CC BY-SA 4.0. Fathomly has changed the layout, removed citation markers, navigation and maintenance notices, and adjusted punctuation. This adapted version is shared under the same license. For references, see the original article.
Images, from Wikimedia Commons:
- Cyclic group.svg by Original: Jakob.scholbach Vector: Pbroks13, CC BY-SA 3.0
Fathomly is not affiliated with or endorsed by the Wikimedia Foundation. Spotted a problem? Tell us.
