惠普實(shí)驗(yàn)室數(shù)學(xué)家破解計(jì)算機(jī)科學(xué)最大難題

P≠NP，一個簡潔的論文標(biāo)題，或許預(yù)示著七大世界數(shù)學(xué)難題之一的P問題（多項(xiàng)式算法）對NP問題（非多項(xiàng)式算法）終于有了答案。據(jù)英國《新科學(xué)家》雜志網(wǎng)站8月11日（北京時間）報(bào)道，美國惠普實(shí)驗(yàn)室的數(shù)學(xué)家維奈·迪奧拉里卡已經(jīng)于6日提交了關(guān)于論證該問題的論文草稿，如果此答案被證實(shí)無誤，那么他將獲得由美國克雷數(shù)學(xué)研究所提供的100萬美元獎金。
P對NP問題是克雷數(shù)學(xué)研究所高額懸賞的七個千禧年難題之一，同時也是計(jì)算機(jī)科學(xué)領(lǐng)域的最大難題，關(guān)系到計(jì)算機(jī)完成一項(xiàng)任務(wù)的速度到底有多快。有些問題計(jì)算起來很容易，利用多項(xiàng)式算法很快能解決，比如求若干個數(shù)的乘積，這類問題被稱作P問題；另一類問題計(jì)算過程比較繁瑣，但驗(yàn)證答案卻很容易，比如把整數(shù)44427進(jìn)行因數(shù)分解，求解過程可能會很費(fèi)時，但如果告訴你答案是177×251，簡單計(jì)算即可驗(yàn)證答案是對的，這類問題就被歸為NP問題。
因此，如果P=NP，那么每個答案很容易得到驗(yàn)證的問題也同樣可以輕松求解。這將對計(jì)算機(jī)安全構(gòu)成巨大威脅，目前加密系統(tǒng)的破解就相當(dāng)于要將一個整數(shù)分解為幾個因數(shù)的乘積，正是其求解過程的繁瑣，才能杜絕黑客的入侵。
而現(xiàn)在，迪奧拉里卡圍繞一個眾所周知的NP問題進(jìn)行論證，給出了P≠NP的答案。這就是布爾可滿足性問題(Boolean Satisfiability Problem)，即詢問一組邏輯陳述是否能同時成立或者互相矛盾。迪奧拉里卡聲稱，他已經(jīng)證明，任何程序都無法迅速解答這個問題，因此，它不是一個P問題。
如果迪奧拉里卡的答案成立，說明P問題和NP問題是不同的兩類問題，這也意味著計(jì)算機(jī)處理問題的能力有限，很多任務(wù)的復(fù)雜性從根本上來說也許是無法簡化的。
對于有些NP問題，包括因數(shù)分解，P≠NP的結(jié)果并沒有明確表示它們是不能被快速解答的；但對于其子集NP完全問題，卻注定了其無法很快得到解決。其中一個著名的例子就是旅行商問題(Travelling Salesman Problem)，即尋找從一個城市到另一個城市的最短路線，答案非常容易驗(yàn)證，不過，如果P≠NP，就沒有計(jì)算機(jī)程序可以迅速給出這個答案。
迪奧拉里卡的論文草稿已經(jīng)得到了復(fù)雜性理論家的認(rèn)可，但一周后公布的論文終稿還將接受嚴(yán)格的審查。(記者陳丹)