词条 | 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. ApplicationsThe 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
Notes1. ^L. Babai, Local expansion of vertex-transitive graphs and random generation in finite groups, Proc. 23rd STOC (1991), 164–174. 2. ^{{cite journal |author1=Frank Celler |author2=Charles R. Leedham-Green |author3=Scott H. Murray |author4=Alice C. Niemeyer |author5=E.A. O'Brien |year=1995 |title=Generating random elements of a finite group |journal= Communications in Algebra |volume=23 |issue=3 |pages=4931–4948 |doi=10.1080/00927879508825509 |citeseerx=10.1.1.43.2250 }} 3. ^{{cite journal |last=Pak |first=Igor |author1-link=Igor Pak |year=2012 |title=Testing commutativity of a group and the power of randomization |journal= LMS Journal of Computation and Mathematics |volume=15 |pages=38–43 |doi=10.1112/S1461157012000046 }} 4. ^See Hоlt et al. (2005). References
2 : Computational group theory|Finite groups |
随便看 |
|
开放百科全书收录14589846条英语、德语、日语等多语种百科知识,基本涵盖了大多数领域的百科知识,是一部内容自由、开放的电子版国际百科全书。