ブラックボックスグループ

計算群論において、ブラックボックス群（ブラックボックス群）とは、要素が長さNのビット列で符号化され、群演算がオラクル（「ブラックボックス」）によって実行される群Gのことである。これらの演算には以下が含まれる。

• 要素gとhの積g · hを取ると、
• 要素gの逆g ⁻¹を取ると、
• g  = 1かどうかを判断する 。

このクラスは、置換群と行列群の両方を含むように定義されています。Gの位数の上限が| G | ≤ 2 N であることから、 Gは有限^であることがわかります。  

ブラックボックス群は、1984 年にBabaiとSzemerédiによって導入されました。 ^{[ 1 ]}これらは、(構成的)群の認識と性質のテストのための形式として使用されました。注目すべきアルゴリズムには、ランダムな群要素を見つけるためのBabai のアルゴリズム^{[ 2 ]}、積置換アルゴリズム[ ^{3 ] 、}および群の可換性のテスト^{[ 4 ]}などがあります。

CGT の初期のアルゴリズムの多く、例えばSchreier–Sims アルゴリズムなどは、群の置換表現を必要とするため、ブラックボックスではありません。他の多くのアルゴリズムは、要素の順序を見つける必要があります。置換群または行列群の要素の順序を見つける効率的な方法があるため (後者の方法は Celler とLeedham-Greenによって1997 年に説明されています)、ブラックボックス群には要素の順序を決定するための別のオラクルが備わっていると仮定するのが一般的な方法です。^{[ 5 ]}

• 暗黙のグラフ
• マトロイドオラクル

• Derek F. Holt、Bettina Eick、Eamonn A. O'Brien、「計算群論ハンドブック」、離散数学とその応用（ボカラトン）。Chapman & Hall/CRC、フロリダ州ボカラトン、2005年 。ISBN 1-58488-372-3
• Ákos Seress、『順列群アルゴリズム』、ケンブリッジ数学論文集、第152巻、ケンブリッジ大学出版局、ケンブリッジ、2003年 。ISBN 0-521-66103-X。
• カントール、ウィリアム・M. ; セレス、アコス (2001).ブラックボックス古典群. アメリカ数学会紀要. 第 708巻.アメリカ数学会. ISBN 978-0-8218-2619-5ISSN 0065-9266​​