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

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

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

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

    如果迪奧拉里卡的答案成立，說明P問題和NP問題是不同的兩類問題，這也意味著計算機處理問題的能力有限，很多任務的復雜性從根本上來說也許是無法簡化的。

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

    迪奧拉里卡的論文草稿已經得到了復雜性理論家的認可，但一周后公布的論文終稿還將接受嚴格的審查。　

    總編輯圈點

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

    P/NP問題：http://baike.baidu.com/view/286218.htm/

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

    P和NP

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

    P和NP相等嗎?

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

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