P≠NP，一個(gè)簡(jiǎn)潔的論文標題，或許預示著(zhù)七大世界數學(xué)難題之一的P問(wèn)題（多項式算法）對NP問(wèn)題（非多項式算法）終于有了答案。據英國《新科學(xué)家》雜志網(wǎng)站8月11日（北京時(shí)間）報道，美國惠普實(shí)驗室的數學(xué)家維奈·迪奧拉里卡已經(jīng)于6日提交了關(guān)于論證該問(wèn)題的論文草稿，如果此答案被證實(shí)無(wú)誤，那么他將獲得由美國克雷數學(xué)研究所提供的100萬(wàn)美元獎金。

    P對NP問(wèn)題是克雷數學(xué)研究所高額懸賞的七個(gè)千禧年難題之一，同時(shí)也是計算機科學(xué)領(lǐng)域的最大難題，關(guān)系到計算機完成一項任務(wù)的速度到底有多快。有些問(wèn)題計算起來(lái)很容易，利用多項式算法很快能解決，比如求若干個(gè)數的乘積，這類(lèi)問(wèn)題被稱(chēng)作P問(wèn)題；另一類(lèi)問(wèn)題計算過(guò)程比較繁瑣，但驗證答案卻很容易，比如把整數44427進(jìn)行因數分解，求解過(guò)程可能會(huì )很費時(shí)，但如果告訴你答案是177×251，簡(jiǎn)單計算即可驗證答案是對的，這類(lèi)問(wèn)題就被歸為NP問(wèn)題。

    因此，如果P=NP，那么每個(gè)答案很容易得到驗證的問(wèn)題也同樣可以輕松求解。這將對計算機安全構成巨大威脅，目前加密系統的破解就相當于要將一個(gè)整數分解為幾個(gè)因數的乘積，正是其求解過(guò)程的繁瑣，才能杜絕黑客的入侵。

    而現在，迪奧拉里卡圍繞一個(gè)眾所周知的NP問(wèn)題進(jìn)行論證，給出了P≠NP的答案。這就是布爾可滿(mǎn)足性問(wèn)題（Boolean Satisfiability Problem），即詢(xún)問(wèn)一組邏輯陳述是否能同時(shí)成立或者互相矛盾。迪奧拉里卡聲稱(chēng)，他已經(jīng)證明，任何程序都無(wú)法迅速解答這個(gè)問(wèn)題，因此，它不是一個(gè)P問(wèn)題。

    如果迪奧拉里卡的答案成立，說(shuō)明P問(wèn)題和NP問(wèn)題是不同的兩類(lèi)問(wèn)題，這也意味著(zhù)計算機處理問(wèn)題的能力有限，很多任務(wù)的復雜性從根本上來(lái)說(shuō)也許是無(wú)法簡(jiǎn)化的。

    對于有些NP問(wèn)題，包括因數分解，P≠NP的結果并沒(méi)有明確表示它們是不能被快速解答的；但對于其子集NP完全問(wèn)題，卻注定了其無(wú)法很快得到解決。其中一個(gè)著(zhù)名的例子就是旅行商問(wèn)題（Travelling Salesman Problem），即尋找從一個(gè)城市到另一個(gè)城市的最短路線(xiàn)，答案非常容易驗證，不過(guò)，如果P≠NP，就沒(méi)有計算機程序可以迅速給出這個(gè)答案。

    迪奧拉里卡的論文草稿已經(jīng)得到了復雜性理論家的認可，但一周后公布的論文終稿還將接受?chē)栏竦膶彶??！?/p>

    總編輯圈點(diǎn)

    較之不久前剛被“拿下”的龐加萊猜想等其他六大數學(xué)難題，本文所議者最是“貼近生活，貼近群眾，貼近實(shí)際”。證明了P與NP的關(guān)系意味著(zhù)數學(xué)計算在方法論范疇的一次撥云見(jiàn)日，進(jìn)而會(huì )給整個(gè)信息產(chǎn)業(yè)帶來(lái)革命性沖擊。每年聲稱(chēng)解決了P與NP問(wèn)題的中外人士無(wú)以計數，可他們大都缺乏基本專(zhuān)業(yè)訓練，因而其“成果”幾乎不具任何價(jià)值。我們毫不懷疑迪奧拉里卡是位嚴肅的科學(xué)家，但仍應以謹慎的態(tài)度耐心等待最終審查結果，畢竟茲事體大。

    P/NP問(wèn)題：http://baike.baidu.com/view/286218.htm/

    P/NP問(wèn)題是在理論信息學(xué)中計算復雜度理論領(lǐng)域里至今沒(méi)有解決的問(wèn)題，它被“克雷數學(xué)研究所”（Clay Mathematics Institute, 簡(jiǎn)稱(chēng)CMI）在千禧年大獎難題中收錄。P/NP問(wèn)題中包含了復雜度類(lèi)P與NP的關(guān)系。1971年史提芬·古克(Stephen A. Cook) 和 Leonid Levin 相對獨立的提出了下面的問(wèn)題,即是否兩個(gè)復雜度類(lèi)P和NP是恒等的（P=NP?）。 

    P和NP

    復雜度類(lèi)P包含所有那些可以由一個(gè)確定型圖靈機在多項式表達的時(shí)間內解決的問(wèn)題；類(lèi)NP由所有其肯定解可以在給定正確信息的多項式時(shí)間內驗證的決定問(wèn)題組成，或者等效的說(shuō)，那些解可以在非確定圖靈機上在多項式時(shí)間內找出的問(wèn)題的集合。很可能，計算理論最大的未解決問(wèn)題就是關(guān)于這兩類(lèi)的關(guān)系的:

    P和NP相等嗎?

    在2002年對于100研究者的調查，61人相信答案是否定的，9個(gè)相信答案是肯定的，22個(gè)不確定，而8個(gè)相信該問(wèn)題可能和現在所接受的公理獨立，所以不可能證明或證否。[1] 對于正確的解答，有一個(gè)1,000,000美元的獎勵。
　　
    NP-完全問(wèn)題(或者叫NPC)的集合在這個(gè)討論中有重大作用，它們可以大致的被描述為那些在NP中最不像在P中的。(確切定義細節請參看NP-完全)理論計算機科學(xué)家現在相信P, NP,和NPC類(lèi)之間的關(guān)系如圖中所示，其中P和NPC類(lèi)不交。
　　
    假設P ≠ NP的復雜度類(lèi)的圖解.如P = NP則三個(gè)類(lèi)相同.本質(zhì)上，P = NP問(wèn)題問(wèn)道：如果是/不是問(wèn)題的正面答案可以很快驗證，其答案是否也可以很快計算？這里有一個(gè)給你找點(diǎn)這個(gè)問(wèn)題的感覺(jué)的例子。給定一個(gè)大數Y,我們可以問(wèn)Y是否是復合數。例如，我們可能問(wèn)53308290611是否有非平凡的因子?；卮鹗强隙ǖ?，雖然手工找出一個(gè)因子很麻煩。從另一個(gè)方面講，如果有人聲稱(chēng)答案是"對，因為224737可以整除53308290611",則我們可以很快用一個(gè)除法來(lái)驗證。驗證一個(gè)數是除數比首先找出除數來(lái)簡(jiǎn)單得多。用于驗證一個(gè)正面答案所需的信息也稱(chēng)為證書(shū)。所以我們的結論是，給定 正確的證書(shū)，問(wèn)題的正面答案可以很快的(也就是，在多項式時(shí)間內)驗證，而這就是這個(gè)問(wèn)題屬于NP的原因。雖然這個(gè)特定的問(wèn)題，最近被證明為也在P類(lèi)中(參看下面的關(guān)于"質(zhì)數在P中"的參考),這一點(diǎn)也不明顯，而且有很多類(lèi)似的問(wèn)題相信不屬于類(lèi)P。

    限制到是/不是問(wèn)題并沒(méi)有改變問(wèn)題；即使我們允許更復雜的答案，最后的問(wèn)題(是否FP = FNP)是等價(jià)的。