今天小編分享的科學經驗：上交大校友獨作！50年零進展算法難題被突破，歡迎閱讀。
半個世紀沒有進展的問題，如今終于有了新突破！
而且是一位華人科學家，單槍匹馬搞定。
來自芝加哥伊利諾伊大學厄巴納 - 香槟分校的Xiaorui Sun，提出了一種新方法，能夠更快速确定群同構。
要知道，讓計算機确定群同構、圖同構是一個非常復雜的問題。
一方面同構問題的解空間通常非常龐大，随着規模增加、需要考慮的可能性也會翻倍增加。另一方面即便在某些情況下兩個結構同構，但是表現形式也會有所不同，給判斷和比較增加了困難。
2015 年，來自芝加哥大學的學者突破了圖同構的計算加速，但是群同構算法的加速，在過去五十年裡都沒有明顯進展。
而 Sun 的最新工作解決了群同構中被視為最難處理的一部分。
什麼是群同構？
首先來理解什麼叫做同構。
按照定義來說，就是兩個數學結構之間存在一種一一對應的映射，它們包含相同的元素，并且元素之間也處于相同的關系中。
比如下面兩個圖雖然看起來不同，但它們是同構的，因為它們的頂點和邊相同，并且點和邊之間的關系一樣。
群同構更加抽象一些。
一個群是由元素（如數字）組成的集合，這些元素可以根據某種運算相互組合，計算的和也包含其中。
舉例如下，在下面兩個群裡，任意兩個整數相加，結果總是另一個整數。
兩個群包含兩個元素，用同樣的特定操作方式，所以它們是同構的。
同構是數學中的一個重要概念，同樣也是計算機科學的基礎。
圖同構和群同構算法目前也都有非常廣泛的應用。
比如圖同構算法可以監測網絡中的惡意攻擊、能分析社交網絡結構關系、用于推薦系統、構建語義圖等。
群同構算法則在密碼學、數學分析與挖掘、影像處理與 CV 等領網域有重要應用。
而在實際應用場景裡，不僅需要确定兩個對象是否同構，還要保障計算速度。
算法的運行時間往往和處理對象中包含多少元素有直接關系，元素越多、時間越長，但是時長并不一定是線性增長的。
假設有兩對群，一對包含 5 個元素，一對包含 10 個元素。确定 10 個元素的群同構問題，花費的時間是 5 個元素群的兩倍？5 的平方？還是 2 的五次方？
這和使用什麼算法有一定關系。
1970 年左右，普林斯頓大學的羅伯特 · 塔爾詹（Robert Tarjan）教授提出了一種方法，它的運行時間為 n 的 log n 次方（n 為元素數量）。
此後半個世紀裡，确定群同構的算法速度就停留在這裡了。由于工具不夠高效，這在一定程度上也影響了群同構的創新拓展。
Sun 提出的方法，正是在這一基礎上，實現了更快的運行時間：
怎麼實現的？
Sun 提出的方法，主要針對類為 2 的 p 群且指數為 p。
它們類似于群，其中兩個元素的乘積是另一個元素，并且乘積結果不受乘法順序改變而改變。
他首先将群轉換為了矩陣，由此将群同構問題轉化為矩陣是否完全相似問題。
而且這裡處理的矩陣具有特殊性質，任意兩個矩陣組合等于另一個矩陣。
這樣一來就将問題轉化為判斷兩個矩陣空間是否為等距。
與此同時，方法中還引入了獨創性的一步，将矩陣空間分為兩個部分。一部分劃定為核心，其中所有的矩陣都是簡單的；其餘部分中的矩陣則特别復雜。
這一步相當于将一個群劃分為只有部分元素的子群。
然後 Sun 将不同算法應用在這些部分裡。處理原則有點像做數獨時的步驟。
先找到最簡單的部分（矩陣空間的核心）解決，然後在難以判斷的部分嘗試所有可能的值——只要這部分不是非常多，處理時間也不會很長。
這樣一來，Sun 就在原有計算速率的基礎上實現了加速，讓群同構計算的速度範疇從指數時間向多項式時間逼近了一些。
更進一步，他的工作還提高了所有群同構算法加速的可能。
據個人官網介紹，Xiaorui Sun 目前是伊利諾大學芝加哥分校計算機系的助理教授。
在此之前，他曾在 UC 伯克利西蒙思研究所、微軟研究院工作過。本碩畢業于上海交通大學，後赴哥倫比亞大學攻讀博士學位，研究方向為算法的設計與分析。
論文地址：
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/
