新算法破解圖同構問題

芝加哥大學的數學和計算機科學教授László Babai 在 11 月 10 日宣布了能有效解決圖同構問題的新算法。斯坦福大學的計算機科學家 Ryan Williams 說，他一開始以為是個玩笑，特地查了下那天是不是愚人節。他認為新的算法有可能是過去十多年計算機科學理論最重要的突破。

Babai 的算法還需要被仔細檢查，他思考這個問題已有 30 多年了。他聲稱算法能在擬多項式時間內判定最復雜的圖，他拒絕接受采訪，表示需要先確保能經受同事們的多輪拷問。麻省大學的理論計算機科學家 Neil Immerman 說，一位數學家在宣布重大發現前沒有遞交書面證據是不同尋常的做法，但 Babai 是非常聰明和可靠的人，是圖同構問題的頂級專家，相信他能證明他的聲明。