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