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

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

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

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

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