本文經AI新媒體量子位（公眾號ID:QbitAI）授權轉載，轉載請聯系出處。

半個世紀沒有進展的問題，如今終于有了新突破！

而且是一位華人科學家，單槍匹馬搞定。

圖片

來自芝加哥伊利諾伊大學厄巴納-香檳分校的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