上交大校友獨作！50年零進展算法難題被突破

明敏 2023-07-02 13:18:51 來源：量子位

明敏 發(fā)自 凹非寺

量子位 | 公眾號 QbitAI

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

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

來自芝加哥伊利諾伊大學厄巴納-香檳分校的Xiaorui Sun，提出了一種新方法，能夠更快速確定群同構(gòu)。

要知道，讓計算機確定群同構(gòu)、圖同構(gòu)是一個非常復(fù)雜的問題。

一方面同構(gòu)問題的解空間通常非常龐大，隨著規(guī)模增加、需要考慮的可能性也會翻倍增加。另一方面即便在某些情況下兩個結(jié)構(gòu)同構(gòu)，但是表現(xiàn)形式也會有所不同，給判斷和比較增加了困難。

2015年，來自芝加哥大學的學者突破了圖同構(gòu)的計算加速，但是群同構(gòu)算法的加速，在過去五十年里都沒有明顯進展。

而Sun的最新工作解決了群同構(gòu)中被視為最難處理的一部分。

什么是群同構(gòu)？

首先來理解什么叫做同構(gòu)。

按照定義來說，就是兩個數(shù)學結(jié)構(gòu)之間存在一種一一對應(yīng)的映射，它們包含相同的元素，并且元素之間也處于相同的關(guān)系中。

比如下面兩個圖雖然看起來不同，但它們是同構(gòu)的，因為它們的頂點和邊相同，并且點和邊之間的關(guān)系一樣。

群同構(gòu)更加抽象一些。

一個群是由元素（如數(shù)字）組成的集合，這些元素可以根據(jù)某種運算相互組合，計算的和也包含其中。

舉例如下，在下面兩個群里，任意兩個整數(shù)相加，結(jié)果總是另一個整數(shù)。

兩個群包含兩個元素，用同樣的特定操作方式，所以它們是同構(gòu)的。

同構(gòu)是數(shù)學中的一個重要概念，同樣也是計算機科學的基礎(chǔ)。

圖同構(gòu)和群同構(gòu)算法目前也都有非常廣泛的應(yīng)用。

比如圖同構(gòu)算法可以監(jiān)測網(wǎng)絡(luò)中的惡意攻擊、能分析社交網(wǎng)絡(luò)結(jié)構(gòu)關(guān)系、用于推薦系統(tǒng)、構(gòu)建語義圖等。

群同構(gòu)算法則在密碼學、數(shù)學分析與挖掘、圖像處理與CV等領(lǐng)域有重要應(yīng)用。

而在實際應(yīng)用場景里，不僅需要確定兩個對象是否同構(gòu)，還要保障計算速度。

算法的運行時間往往和處理對象中包含多少元素有直接關(guān)系，元素越多、時間越長，但是時長并不一定是線性增長的。

假設(shè)有兩對群，一對包含5個元素，一對包含10個元素。確定10個元素的群同構(gòu)問題，花費的時間是5個元素群的兩倍？5的平方？還是2的五次方？

這和使用什么算法有一定關(guān)系。

1970年左右，普林斯頓大學的羅伯特·塔爾詹（Robert Tarjan）教授提出了一種方法，它的運行時間為n的log n次方（n為元素數(shù)量）。

此后半個世紀里，確定群同構(gòu)的算法速度就停留在這里了。由于工具不夠高效，這在一定程度上也影響了群同構(gòu)的創(chuàng)新拓展。

Sun提出的方法，正是在這一基礎(chǔ)上，實現(xiàn)了更快的運行時間：

怎么實現(xiàn)的？

Sun提出的方法，主要針對類為2的p群且指數(shù)為p。

它們類似于群，其中兩個元素的乘積是另一個元素，并且乘積結(jié)果不受乘法順序改變而改變。

他首先將群轉(zhuǎn)換為了矩陣，由此將群同構(gòu)問題轉(zhuǎn)化為矩陣是否完全相似問題。

而且這里處理的矩陣具有特殊性質(zhì)，任意兩個矩陣組合等于另一個矩陣。

這樣一來就將問題轉(zhuǎn)化為判斷兩個矩陣空間是否為等距。

與此同時，方法中還引入了獨創(chuàng)性的一步，將矩陣空間分為兩個部分。一部分劃定為核心，其中所有的矩陣都是簡單的；其余部分中的矩陣則特別復(fù)雜。

這一步相當于將一個群劃分為只有部分元素的子群。

然后Sun將不同算法應(yīng)用在這些部分里。處理原則有點像做數(shù)獨時的步驟。

先找到最簡單的部分（矩陣空間的核心）解決，然后在難以判斷的部分嘗試所有可能的值——只要這部分不是非常多，處理時間也不會很長。

這樣一來，Sun就在原有計算速率的基礎(chǔ)上實現(xiàn)了加速，讓群同構(gòu)計算的速度范疇從指數(shù)時間向多項式時間逼近了一些。

更進一步，他的工作還提高了所有群同構(gòu)算法加速的可能。

據(jù)個人官網(wǎng)介紹，Xiaorui Sun目前是伊利諾大學芝加哥分校計算機系的助理教授。

在此之前，他曾在UC伯克利西蒙思研究所、微軟研究院工作過。本碩畢業(yè)于上海交通大學，后赴哥倫比亞大學攻讀博士學位，研究方向為算法的設(shè)計與分析。

論文地址：
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/