不可勝數

數學高手難免也出錯

幾經曲折,圖同構問題透出曙光!

撰文/李國偉

不可勝數

數學高手難免也出錯

幾經曲折,圖同構問題透出曙光!

撰文/李國偉


數學研究要求邏輯推理完美無瑕,不過完美的標準並非亙古不變,經常反映當代數學思想的局限。例如,牛頓與萊布尼茲借助關於「無窮小」的直覺想像,在17世紀末各自發明了微積分,但是微積分的嚴謹邏輯基礎直到19世紀才建立。


目前數學家對於論證的邏輯標準有高度共識,努力朝此標準邁進。然而就算是數學高手,偶爾也會有思慮欠周、失誤的時候。1993年6月威爾斯(Andrew Wiles)在一系列演講結尾,輕描淡寫地說已經證明了費馬猜想,一夕之間吸引全球數學家目光。但是同年8月,就有人找出論證的漏洞。結果威爾斯花了一年修改,還找了一位優秀博士生泰勒(Richard Taylor)合作,總算得到完滿的結局。


無獨有偶,最近又發生一項高手犯錯的實例,相當受到數學界矚目。


從幾何的觀點看下方兩張圖,可以發現形狀不一樣。不過我們在此只討論稱為「結點」的小圓圈之間,用稱為「邊線」的線段連接的狀況,那些在結點之外的邊線交錯無關緊要,邊線是直是曲也沒有影響。於是問題來了,如果兩圖的結點與邊線數量相同,如何知道連接關係是相同還是相異?換句話說,我們在平面上畫了圖A與圖B,可否判定有無函數F把圖A與圖B的結點一一對應起來,使得兩結點x與y在圖A裡有邊線相連,若且唯若F(x)與F(y)在圖B裡有邊線相連?這個問題稱為「圖同構問題」。例如把下方兩張圖中相同字母及數字對應起來,得以驗證兩張圖其實是同構的。


一種解決圖同構問題的簡單想法,就是列舉圖A與圖B結點之間所有的對應情況,逐一檢查是否保持有關聯性。然而,當結點逐步增多、邊線漸次複雜後,要檢查的對應數可能會暴增,就算用目前最好的程式在最快的電腦上運算,仍有可能耗費億萬年,實質上等於無法解決。


對於有限結構的計算,如果能設計出解決問題的程式,使得計算時間控制在輸入資料大小的多項式時間內完成,就歸入所謂的P類。理論上,此類問題可以有效率求解。另外一類問題屬於所謂NP完備類,直到目前為止,還找不到多項式時間的算法來解決。也就是說,現行的解法效率都極度不佳。1998年美國克萊數學研究所提出七個百萬美元的世紀徵答題,其中便包括了判別P類與NP完備類是否真的有區別。


圖同構問題的重要性在於難以判定它到底是P類?NP完備類?或是介於其間的其他類?大家都不敢冀望近期內有本質上的突破。可是2015年11月芝加哥大學教授巴拜伊(Laszlo Babai)公開宣佈,找到所謂「準多項式時間」(quasi-polynomial time)算法,雖然還不能把圖同構問題歸入P類,但已經是30餘年來此問題的最大進展。因為巴拜伊是聲名卓著的數學家,他的最新結果震驚了學界。


法國著名的布爾巴基(Nicolas Bourbaki)討論班定期研討最近的重要數學進展,慣例不邀請做出卓越成果的數學家本人現身說法。德國數學家海爾福果特(H. A. Helfgott)應邀在討論班報告巴拜伊的結果,不過他於今年1月4日宣稱發現論文的漏洞。巴拜伊旋即公開承認出錯,並且在甚短時間內修正。經過海爾福果特的嚴格檢查,新的證明終於在布爾巴基討論班上受到認可。這回高手巴拜伊的失誤,總算又以喜劇收場。對於判定圖同構問題的實際難度來說,好像透出一些曙光。


更多相關文章

2017年10月188期這不只是女性議題 雜誌訂閱

本期最新文章