In
computational group theory
In mathematics, computational group theory is the study of
group (mathematics), groups by means of computers. It is concerned
with designing and analysing algorithms and
data structures to compute information about groups. The subject
has attracted ...
, a black box group (black-box group) is a
group
A group is a number of persons or things that are located, gathered, or classed together.
Groups of people
* Cultural group, a group whose members share the same cultural identity
* Ethnic group, a group whose members share the same ethnic ide ...
''G'' whose elements are encoded by
bit strings of length ''N'', and group operations are performed by an
oracle
An oracle is a person or agency considered to provide wise and insightful counsel or prophetic predictions, most notably including precognition of the future, inspired by deities. As such, it is a form of divination.
Description
The word '' ...
(the "
black box
In science, computing, and engineering, a black box is a system which can be viewed in terms of its inputs and outputs (or transfer characteristics), without any knowledge of its internal workings. Its implementation is "opaque" (black). The te ...
"). 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 group
In mathematics, a permutation group is a group ''G'' whose elements are permutations of a given set ''M'' and whose group operation is the composition of permutations in ''G'' (which are thought of as bijective functions from the set ''M'' to it ...
s and the
matrix group In mathematics, a matrix group is a group ''G'' consisting of invertible matrices over a specified field ''K'', with the operation of matrix multiplication. A linear group is a group that is isomorphic to a matrix group (that is, admitting a fa ...
s. The upper bound on the
order of ''G'' given by , ''G'', ≤ 2
''N'' shows that ''G'' is
finite
Finite is the opposite of infinite. It may refer to:
* Finite number (disambiguation)
* Finite set, a set whose cardinality (number of elements) is some natural number
* Finite verb, a verb form that has a subject, usually being inflected or marke ...
.
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
In computer science, a property testing algorithm for a decision problem is an algorithm whose query complexity to its input is much smaller than the instance size of the problem. Typically property testing algorithms are used to distinguish if s ...
''. 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 The Schreier–Sims algorithm is an algorithm in computational group theory, named after the mathematicians Otto Schreier and Charles Sims. This algorithm can find the order of a finite permutation group, test membership (is a given permutation c ...
, require a
permutation representation
In mathematics, the term permutation representation of a (typically finite) group G can refer to either of two closely related notions: a representation of G as a group of permutations, or as a group of permutation matrices. The term also refers ...
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.
[See Hоlt et al. (2005).]
See also
*
Implicit graph
In the study of graph algorithms, an implicit graph representation (or more simply implicit graph) is a graph whose vertices or edges are not represented as explicit objects in a computer's memory, but rather are determined algorithmically from so ...
*
Matroid oracle
In mathematics and computer science, a matroid oracle is a subroutine through which an algorithm may access a matroid, an abstract combinatorial structure that can be used to describe the linear dependencies between vectors in a vector space or ...
Notes
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.
* Ákos Seress, ''Permutation group algorithms'', Cambridge Tracts in Mathematics, vol. 152, Cambridge University Press, Cambridge, 2003. .
* {{cite book , authorlink1=William Kantor , title=Black Box Classical Groups , series=Memoirs of the American Mathematical Society , issn=0065-9266 , volume=708 , first1=William M. , last1=Kantor , first2=Ákos , last2=Seress , publisher=
American Mathematical Society
The American Mathematical Society (AMS) is an association of professional mathematicians dedicated to the interests of mathematical research and scholarship, and serves the national and international community through its publications, meetings, ...
, year=2001 , isbn=978-0-8218-2619-5
Computational group theory
Finite groups