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

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

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

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

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