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

近日，芝加哥伊利諾伊大學(xué)厄巴納香檳分校的一名華人科學(xué)家提出了一種新的方法，可以通過這種方法更快速的確定群同構(gòu)，這個問題長達(dá)半個世紀(jì)都沒有任何進(jìn)展，如今已經(jīng)迎來了新的突破，同構(gòu)問題的解空間通常是比較龐大的，隨著團(tuán)構(gòu)規(guī)模的增加需要考慮的可能性也會翻倍提升，另一方面來看即便在某個情況下兩個結(jié)構(gòu)同構(gòu)，但是他們兩個呈現(xiàn)出來的表現(xiàn)形式也會有所區(qū)別，對整體的判斷也會造成更多的困難。

在2015年，來自芝加哥大學(xué)的學(xué)者就已經(jīng)突破了圖同構(gòu)的加速計算，但是對群同構(gòu)算法的加速一直都沒有取得太好的進(jìn)展，同構(gòu)按照定義來說，就是將兩個數(shù)學(xué)結(jié)構(gòu)之間是存在一種相互對應(yīng)的映射關(guān)系，他們包含的各種元素也會處于相同的關(guān)系中，比如有兩個圖形看起來不同，但是他們實際是同構(gòu)的，因為他們的頂點和邊是屬于相同的位置，而且點和邊之間的關(guān)系也是屬于同樣的。

這個關(guān)系可以說是數(shù)學(xué)理念中的一個重要概念，也是計算機(jī)科學(xué)的基礎(chǔ)之一，在目前廣的各個領(lǐng)域都有非常廣泛的應(yīng)用空間，比如使用圖同構(gòu)算法以去監(jiān)測網(wǎng)絡(luò)中的一些惡意攻擊，也能夠分析社交網(wǎng)絡(luò)的結(jié)構(gòu)關(guān)系，使用群同構(gòu)算法，可以在密碼學(xué)，數(shù)學(xué)分析以及圖像處理方面取得更重要的作用，在實際運(yùn)用場景中，不僅需要去確定兩個對象是否會是同構(gòu)現(xiàn)象，也需要去保障整體的計算速度。

這位華人科學(xué)家所提出的構(gòu)思，主要是將群轉(zhuǎn)換成了矩陣，將群同構(gòu)的問題轉(zhuǎn)化成矩陣是否是相似的問題，在這個問題中，處理的矩陣具有一些特殊性質(zhì)，任意兩個矩陣組合就會演變成另外一個矩陣，這樣一來，就會將問題轉(zhuǎn)化成判斷兩個矩陣空間是否等距的問題，在這個問題探討的過程中，還引入了一些獨創(chuàng)性的內(nèi)容，從而提高了所有群同構(gòu)算法的加速可能。