明敏 發自 凹非寺
半個世紀沒有進展的問題，如今終於有了新突破！
而且是一位華人科學家，單槍匹馬搞定。
來自芝加哥伊利諾伊大學厄巴納-香檳分校的Xiaorui Sun，提出了一種新方法，能夠更快速確定群同構。
要知道，讓計算機確定群同構、圖同構是一個非常複雜的問題。
一方面同構問題的解空間通常非常龐大，隨著規模增加、需要考慮的可能性也會翻倍增加。另一方面即便在某些情況下兩個結構同構，但是表現形式也會有所不同，給判斷和比較增加了困難。
2015年，來自芝加哥大學的學者突破了圖同構的計算加速，但是群同構演算法的加速，在過去五十年裡都沒有明顯進展。
而Sun的最新工作解決了群同構中被視為最難處理的一部分。
什麼是群同構？
首先來理解什麼叫做同構。
按照定義來說，就是兩個數學結構之間存在一種一一對應的對映，它們包含相同的元素，並且元素之間也處於相同的關係中。
比如下面兩個圖雖然看起來不同，但它們是同構的，因為它們的頂點和邊相同，並且點和邊之間的關係一樣。
群同構更加抽象一些。
一個群是由元素（如數字）組成的集合，這些元素可以根據某種運算相互組合，計算的和也包含其中。
舉例如下，在下面兩個群裡，任意兩個整數相加，結果總是另一個整數。
兩個群包含兩個元素，用同樣的特定操作方式，所以它們是同構的。
同構是數學中的一個重要概念，同樣也是電腦科學的基礎。
圖同構和群同構演算法目前也都有非常廣泛的應用。
比如圖同構演算法可以監測網路中的惡意攻擊、能分析社群網路結構關係、用於推薦系統、構建語義圖等。
群同構演算法則在密碼學、數學分析與挖掘、圖像處理與CV等領域有重要應用。
而在實際應用場景裡，不僅需要確定兩個對象是否同構，還要保障計算速度。
演算法的運行時間往往和處理對象中包含多少元素有直接關係，元素越多、時間越長，但是時長並不一定是線性增長的。
假設有兩對群，一對包含5個元素，一對包含10個元素。確定10個元素的群同構問題，花費的時間是5個元素群的兩倍？5的平方？還是2的五次方？
這和使用什麼演算法有一定關係。
1970年左右，普林斯頓大學的羅伯特·塔爾詹（Robert Tarjan）教授提出了一種方法，它的運行時間為n的log n次方（n為元素數量）。
此後半個世紀裡，確定群同構的演算法速度就停留在這裡了。由於工具不夠高效，這在一定程度上也影響了群同構的創新拓展。
Sun提出的方法，正是在這一基礎上，實現了更快的運行時間：
怎麼實現的？
Sun提出的方法，主要針對類為2的p群且指數為p。
它們類似於群，其中兩個元素的乘積是另一個元素，並且乘積結果不受乘法順序改變而改變。
他首先將群轉換為了矩陣，由此將群同構問題轉化為矩陣是否完全相似問題。
而且這裡處理的矩陣具有特殊性質，任意兩個矩陣組合等於另一個矩陣。
這樣一來就將問題轉化為判斷兩個矩陣空間是否為等距。
與此同時，方法中還引入了獨創性的一步，將矩陣空間分為兩個部分。一部分劃定為核心，其中所有的矩陣都是簡單的；其餘部分中的矩陣則特別複雜。
這一步相當於將一個群劃分為只有部分元素的子群。
然後Sun將不同演算法應用在這些部分裡。處理原則有點像做數獨時的步驟。
先找到最簡單的部分（矩陣空間的核心）解決，然後在難以判斷的部分嘗試所有可能的值——只要這部分不是非常多，處理時間也不會很長。
這樣一來，Sun就在原有計算速率的基礎上實現了加速，讓群同構計算的速度範疇從指數時間向多項式時間逼近了一些。
更進一步，他的工作還提高了所有群同構演算法加速的可能。
據個人官網介紹，Xiaorui Sun目前是伊利諾大學芝加哥分校計算機系的助理教授。
在此之前，他曾在UC柏克萊西蒙思研究所、微軟研究院工作過。本碩畢業於上海交通大學，後赴哥倫比亞大學攻讀博士學位，研究方向為演算法的設計與分析。
論文地址：
https://arxiv.org/abs/2303.15412
參考連結：
[1]https://www.quantamagazine.org/computer-scientists-inch-closer-to-major-algorithmic-goal-20230623/ [2]https://www.cs.uic.edu/~xiaorui/