[美]Lance Fortnow?
2017.10.26? ?課堂展示材料
2016年，捷克數(shù)學(xué)家米萊娜·帕維爾用郵件轉(zhuǎn)發(fā)了一個她認(rèn)為理論上能有效解決NP問題的算法。計算機科學(xué)和數(shù)學(xué)界經(jīng)過仔細驗證，一致認(rèn)為米萊娜所言不虛，算法確實解決了偉大的P/NP問題。米萊娜將算法發(fā)表成論文，文章本身的名字很低調(diào)，叫做“論一個庫克沒有解決的問題”（On an Open Problem of Cook），而《紐約時報》介紹文章的標(biāo)題更為直白，恰如其分地表明了它的價值：“P=NP”。
2018年，米萊娜成為第一個獲得數(shù)學(xué)領(lǐng)域最高榮譽（菲爾茲獎）的女性。一年后克雷數(shù)學(xué)研究所獎給米萊娜一張價值100萬美元的支票。她成為繼格里高利·佩雷爾曼之后第二個成功解決千禧年數(shù)學(xué)難題的人。不像佩雷爾曼，她高興地收下了獎金，并將其中一部分（數(shù)額未知）捐給了故鄉(xiāng)布拉格的大學(xué)作為獎學(xué)金。雖然米萊娜的算法在理論上是一個突破，但因為實際執(zhí)行時間過長而缺乏實用價值。2017年，俄羅斯計算機科學(xué)家明斯克·波洛夫采用一種巧妙的方法改良了米萊娜的算法，從而大幅改進了算法的執(zhí)行效率，然而還是不夠?qū)嵱谩?/p>
一年后在中國，清華大學(xué)的一群本科生仔細優(yōu)化了明斯克的代碼，在當(dāng)時世界上最快的超級計算機上運行它。他們在幾天之內(nèi)就解決了較大規(guī)模的團問題和其他幾個常見的NP問題。清華大學(xué)開始與波音、戴姆勒-奔馳等工業(yè)巨頭簽約，幫助這些公司解決一些棘手的優(yōu)化問題。他們幫助波音為新797客機設(shè)計出了更好的機翼，使得客機能直接從倫敦飛到悉尼。
史蒂夫·弗蘭克是伊利諾伊大學(xué)的博士生，此時在清華做一學(xué)期的訪問學(xué)者，他有幸參與了項目的研究工作?；氐揭晾Z伊州的厄巴納后，他向?qū)熢V苦，無論他們?nèi)绾蝺?yōu)化，還是要花幾天時間才能解決一個中等規(guī)模的NP問題?！叭绻阌龅綗羯瘢軡M足你一個愿望，你會許什么愿？”導(dǎo)師說。
“不知道?！笔返俜蚧卮?。
“讓它給你一個能滿足你所有愿望的燈神！”
史蒂夫腦中一亮。他知道一定存在一個能更好解決團問題的算法，而他自己想不出這個算法。但是他遇到了燈神——清華的代碼，他可以用很快的速度搜索指數(shù)級數(shù)量的可能算法。所以他基于清華的例程寫了一個搜索更好的NP問題算法的程序。他獲準(zhǔn)可以使用位于伊利諾伊大學(xué)的國家超級計算應(yīng)用中心（NCSA）的計算資源。經(jīng)過幾周的計算，他的工作初見成效。他找到了一個比清華的算法性能高5%的算法。這一結(jié)果發(fā)篇論文綽綽有余，但不會產(chǎn)生轟動效應(yīng)。
他的導(dǎo)師淡淡地說：“用新算法再試一次。”
于是史蒂夫用他的新算法找到了一個更快的解決NP問題的算法。幾周后他獲得了20%的性能提升。
但他的導(dǎo)師還不滿意：“再試一次?！?/p>
史蒂夫這樣回答：“我為什么不編個程序讓計算機自動使用找到的算法來查找更好的算法呢？”
導(dǎo)師的目光變得異樣起來，仿佛在說你終于開竅了，又仿佛在說，這么明顯的事你怎么現(xiàn)在才想到。
史蒂夫回到辦公室，開始寫一個算法，讓計算機能自動利用搜索到的更快的算法去查找比當(dāng)前算法更快的算法，這樣一直找下去，直到性能無法提升為止。史蒂夫的一個同事問他是否擔(dān)心天網(wǎng)效應(yīng)。
“天網(wǎng)是啥？”“當(dāng)計算機變得足夠聰明，有了自我意識，它就會接管世界，就像《終結(jié)者》系列電影里的超級計算機‘天網(wǎng)’一樣。”
“不，只是計算機代碼而已，不用擔(dān)心?！?/p>
史蒂夫?qū)懞昧舜a，最后一次在NCSA的超級計算機上運行它。隨著迭代次數(shù)的增加，由計算機自動生成的求解NP問題的算法性能變得越來越好，最后在停止時，生成了一個有4200萬行機器碼的讓人費解的程序。它求解NP問題的速度，那是相當(dāng)快。（順便說一句，計算機依然沒有自我意識。）某高校出版社將這個算法自豪地稱為“厄巴納算法”，后來這個名字被保留了下來。
伊利諾伊大學(xué)的數(shù)學(xué)家們開始率先使用厄巴納算法，用它來證明剩下的千禧年數(shù)學(xué)難題。證明過程是計算機生成的，復(fù)雜到人類幾乎無法理解?？死讛?shù)學(xué)研究所很快發(fā)表聲明，不再接受基于米萊娜·帕維爾發(fā)現(xiàn)的百萬美元算法衍生出來的任何算法的數(shù)學(xué)證明。
許多試圖以許可證和買斷方式獲得厄巴納算法的公司都陷入了訴訟泥潭，因為與算法有關(guān)的各方——資助米萊娜研究的捷克政府、史蒂夫·弗蘭克、史蒂夫的導(dǎo)師以及NCSA，都主張自己對厄巴納算法的所有權(quán)。
世界貿(mào)易組織在認(rèn)識到該算法的重大意義后，要求公開厄巴納算法，供全人類共同享用，相關(guān)各方將得到合理的補償，并成立專門委員會落實。2019年10月23日，厄巴納算法對所有人公開了。
從此，世界發(fā)生了一系列戲劇性的變化……
《數(shù)說》，說更有意思的數(shù)學(xué)
