上海交通大学卒業生によるソロ作品！ 50年間のゼロ進歩アルゴリズム問題が解決された

この記事はAI新メディアQuantum Bit（公開アカウントID：QbitAI）より許可を得て転載しています。転載の際は出典元にご連絡ください。

半世紀もの間、進展がなかった問題が、ついに新たな突破口を開きました！

そしてそれを独力で成し遂げたのは中国の科学者だった。

写真

シカゴのイリノイ大学アーバナ・シャンペーン校のXiaorui Sun 氏は、群同型性をより迅速に判定する新しい方法を提案した。

ご存知のように、コンピューターにグループ同型性とグラフ同型性を判定させるのは非常に複雑な問題です。

一方、同型問題の解空間は通常非常に大きく、規模が大きくなるにつれて、考慮する必要がある可能性も倍増します。一方、2 つの構造が同型であっても、表現が異なる場合があり、判断や比較が難しくなることがあります。

2015年にシカゴ大学の学者たちはグラフ同型性の計算高速化において画期的な成果を上げましたが、過去50年間にグループ同型性アルゴリズムの高速化には大きな進歩がありませんでした。

サン氏の最新の研究は、群同型性の最も難しい部分と考えられているものに取り組んでいる。

グループ同型性とは何ですか?

まず、同型性とは何かを理解しましょう。

定義により、2 つの数学的構造の間には 1 対 1 のマッピングがあり、同じ要素が含まれ、要素は同じ関係にあります。

たとえば、以下の 2 つのグラフは見た目は異なりますが、頂点と辺が同じであり、点と辺の関係も同じであるため、同型です。

写真

グループ同型性はもう少し抽象的です。

グループとは、要素の合計など、何らかの演算に従って互いに組み合わせることができる要素 (数値など) の集合です。

たとえば、次の 2 つのグループでは、任意の 2 つの整数を加算すると、結果は常に別の整数になります。

2 つのグループには 2 つの要素が含まれ、同じ特定の演算を使用するため、それらは同型です。

写真

同型性は数学における重要な概念であり、コンピューターサイエンスの基礎でもあります。

グラフ同型性アルゴリズムとグループ同型性アルゴリズムは現在広く使用されています。

たとえば、グラフ同型性アルゴリズムは、ネットワークに対する悪意のある攻撃を監視したり、ソーシャル ネットワークの構造的関係を分析したり、推奨システムで使用したり、セマンティック グラフを構築したりすることができます。

グループ同型アルゴリズムは、暗号化、数学的分析とマイニング、画像処理、CV において重要な用途があります。

実際のアプリケーション シナリオでは、2 つのオブジェクトが同型であるかどうかを判断するだけでなく、計算速度を確保することも必要です。

アルゴリズムの実行時間は、多くの場合、処理オブジェクトに含まれる要素の数に直接関係します。要素の数が多いほど時間がかかりますが、実行時間は必ずしも直線的に増加するわけではありません。

2 組のグループがあり、1 組には 5 つの要素が含まれ、もう 1 組には 10 の要素が含まれるとします。 10 個の要素のグループの同型性の問題を決定するのに、5 個の要素のグループの 2 倍の時間がかかりますか? 5の2乗？それとも2の5乗ですか?

これは使用されるアルゴリズムと関係があります。

1970 年頃、プリンストン大学のロバート・タージャン教授は、n log n 時間 (n は要素数) で実行される方法を提案しました。

その後半世紀にわたって、群同型性を決定するアルゴリズムの速度はこのレベルに留まりました。ツールが十分に効率的ではないため、グループ同型の革新的な拡張にも一定の影響が出ています。

これを基にした Sun の方法は、より高速な実行時間を実現します。

それはどのように達成されるのでしょうか?

Sun が提案した方法は、主にクラス 2 およびインデックス p の p グループを対象としています。

2 つの要素の積が別の要素となり、乗算の順序を変えても積が変化しないという点で、群と似ています。

彼はまず群を行列に変換し、それによって群同型の問題を行列が完全に類似しているかどうかという問題に変換しました。

さらに、ここで扱われる行列は特殊な特性を持ち、2 つの行列の任意の組み合わせは別の行列と等しくなります。

これにより、問題は 2 つの行列空間が等長であるかどうかを判断するものになります。

同時に、行列空間を 2 つの部分に分割する独自のステップが方法に導入されます。 1 つの部分はコアとして指定され、すべてのマトリックスは単純ですが、残りの部分のマトリックスは特に複雑です。

このステップは、グループを一部の要素のみを含むサブグループに分割することと同じです。

その後、Sun はこれらの部分に異なるアルゴリズムを適用しました。処理原理は、数独を解くときの手順に少し似ています。

最初に解決するのが最も簡単な部分（行列空間のコア）を見つけて、次に難しい部分で可能なすべての値を試します。この部分がそれほど大きくない限り、処理時間はそれほど長くなりません。

このようにして、Sun は元の計算速度に基づく加速を実現し、群同型計算の速度範囲を指数時間から多項式時間まで引き上げました。

さらに、彼の研究により、すべてのグループ同型アルゴリズムを高速化できる可能性が向上しました。

個人の公式ウェブサイトによると、サン・シャオルイ氏は現在、イリノイ大学シカゴ校のコンピューターサイエンス学部の助教授を務めている。

それ以前は、カリフォルニア大学バークレー校のサイモンズ研究所とマイクロソフトリサーチで勤務していました。彼は上海交通大学で学士号と修士号を取得し、その後コロンビア大学に進学して博士号を取得し、アルゴリズムの設計と分析を研究分野としました。

論文アドレス: https://arxiv.org/abs/2303.15412