共役クラスを見つけるための最も速いアルゴリズムは何ですか?

表表現によって$ n $の有限群$ G $が与えられたとする。グループ$ G
$の共用クラスを計算したいと思います。簡単なアルゴリズムは、$ O(n ^ 2)$演算($ b = g ^ { – 1} g
$型チェック)をとるようです。 $ G $ check $ b = g ^ { – 1} a g
$の要素の各ペア(すべてのペアに対して行う必要はないことがわかります)について私はインターネットで検索しようとしましたが、一般的にそれについて具体的なものは見つかりませんでした。

Question : What is the fastest known algorithm
for finding conjugacy classes?

ベストアンサー

私はこれがRAM上の$ O(n log n)$でできると信じています。$ n = | G |
$;私は参照を知らないので、ここでそれを書き留めます(しかし、確かにこれはオリジナルではありません)。これが最も速いのかどうかも分かりませんが、明らかに$
Omega(n)$より速くすることはできませんので、近いといけません。

整数$ 1、 dotsc、n $によってグループ要素がコンピュータ内で示され、G $の$ g_iは整数$ i
$に対応するグループ要素であると仮定しましょう。 $ g_1 $がIDであるWLOGを仮定します。

1)$ O(n log n)$時間でサイズ$ leq log_2 n $の生成集合$ Gamma
$を求める:

G = list of group elements
Gamma = []
Gr = new graph with vertex set G and no edges          //O(n) steps
found = new array of length n, initialized to all false//O(n) steps
for i = 2 to n://never need to add identity to generating set
    if not found[i] then
        Gamma.append(i)
       //Now update the graph Gr by adding new edges
       //Corresponding to the new generator G[i]=g_i
        for each vertex g in Gr:
            Gr.addEdge(g,g*G[i])
        end for
        do BFS on Gr starting from 1, ignoring any vertices already found
        (for any vertex j encountered, this sets found[j]=true)
    end if
end for

2)次のスパースグラフを作成します(すなわち、エッジリスト表現では、密接な隣接行列表現をはしません)。$ G
$の要素であり、 (g、h)$ if $ h = ガンマg ガンマ^ { – 1} $である。これは$ n $頂点と最大次数$
O( log n)$のグラフです。その結合されたコンポーネントは共役クラスであり、それらを見つけることは、時間$ O(v + e)=
O(n + n log n)= O(n log n)$のBFSによって行うことができる。

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です