上交大校友獨(dú)作！50年零進(jìn)展算法難題被突破

明敏 2023-07-02 13:18:51 來(lái)源：量子位

明敏 發(fā)自 凹非寺

量子位 | 公眾號(hào) QbitAI

半個(gè)世紀(jì)沒(méi)有進(jìn)展的問(wèn)題，如今終于有了新突破！

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

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

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

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

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

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

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

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

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

比如下面兩個(gè)圖雖然看起來(lái)不同，但它們是同構(gòu)的，因?yàn)樗鼈兊捻旤c(diǎn)和邊相同，并且點(diǎn)和邊之間的關(guān)系一樣。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

怎么實(shí)現(xiàn)的？

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

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

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

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

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

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

這一步相當(dāng)于將一個(gè)群劃分為只有部分元素的子群。

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

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

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

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

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

在此之前，他曾在UC伯克利西蒙思研究所、微軟研究院工作過(guò)。本碩畢業(yè)于上海交通大學(xué)，后赴哥倫比亞大學(xué)攻讀博士學(xué)位，研究方向?yàn)樗惴ǖ脑O(shè)計(jì)與分析。

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