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ù)的乘積，這類問(wèn)題被稱作P問(wèn)題；另一類問(wèn)題計(jì)算過(guò)程比較繁瑣，但驗(yàn)證答案卻很容易，比如把整數(shù)44427進(jìn)行因數(shù)分解，求解過(guò)程可能會(huì)很費(fèi)時(shí)，但如果告訴你答案是177×251，簡(jiǎn)單計(jì)算即可驗(yàn)證答案是對(duì)的，這類問(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)題是不同的兩類問(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)可，但一周后公布的論文終稿還將接受嚴(yán)格的審查。
總編輯圈點(diǎn)
較之不久前剛被“拿下”的龐加萊猜想等其他六大數(shù)學(xué)難題，本文所議者最是“貼近生活，貼近群眾，貼近實(shí)際”。證明了P與NP的關(guān)系意味著數(shù)學(xué)計(jì)算在方法論范疇的一次撥云見(jiàn)日，進(jìn)而會(huì)給整個(gè)信息產(chǎn)業(yè)帶來(lái)革命性沖擊。每年聲稱解決了P與NP問(wèn)題的中外人士無(wú)以計(jì)數(shù)，可他們大都缺乏基本專業(yè)訓(xùn)練，因而其“成果”幾乎不具任何價(jià)值。我們毫不懷疑迪奧拉里卡是位嚴(yán)肅的科學(xué)家，但仍應(yīng)以謹(jǐn)慎的態(tài)度耐心等待最終審查結(jié)果，畢竟茲事體大。
P/NP問(wèn)題：http://baike.baidu.com/view/286218.htm/
P/NP問(wèn)題是在理論信息學(xué)中計(jì)算復(fù)雜度理論領(lǐng)域里至今沒(méi)有解決的問(wèn)題，它被“克雷數(shù)學(xué)研究所”（Clay Mathematics Institute, 簡(jiǎn)稱CMI）在千禧年大獎(jiǎng)難題中收錄。P/NP問(wèn)題中包含了復(fù)雜度類P與NP的關(guān)系。1971年史提芬·古克(Stephen A. Cook) 和 Leonid Levin 相對(duì)獨(dú)立的提出了下面的問(wèn)題,即是否兩個(gè)復(fù)雜度類P和NP是恒等的（P=NP?）。
P和NP
復(fù)雜度類P包含所有那些可以由一個(gè)確定型圖靈機(jī)在多項(xiàng)式表達(dá)的時(shí)間內(nèi)解決的問(wèn)題；類NP由所有其肯定解可以在給定正確信息的多項(xiàng)式時(shí)間內(nèi)驗(yàn)證的決定問(wèn)題組成，或者等效的說(shuō)，那些解可以在非確定圖靈機(jī)上在多項(xiàng)式時(shí)間內(nèi)找出的問(wèn)題的集合。很可能，計(jì)算理論最大的未解決問(wèn)題就是關(guān)于這兩類的關(guān)系的:
P和NP相等嗎?
在2002年對(duì)于100研究者的調(diào)查，61人相信答案是否定的，9個(gè)相信答案是肯定的，22個(gè)不確定，而8個(gè)相信該問(wèn)題可能和現(xiàn)在所接受的公理獨(dú)立，所以不可能證明或證否。[1] 對(duì)于正確的解答，有一個(gè)1,000,000美元的獎(jiǎng)勵(lì)。
NP-完全問(wèn)題(或者叫NPC)的集合在這個(gè)討論中有重大作用，它們可以大致的被描述為那些在NP中最不像在P中的。(確切定義細(xì)節(jié)請(qǐng)參看NP-完全)理論計(jì)算機(jī)科學(xué)家現(xiàn)在相信P, NP,和NPC類之間的關(guān)系如圖中所示，其中P和NPC類不交。
假設(shè)P ≠ NP的復(fù)雜度類的圖解.如P = NP則三個(gè)類相同.本質(zhì)上，P = NP問(wèn)題問(wèn)道：如果是/不是問(wèn)題的正面答案可以很快驗(yàn)證，其答案是否也可以很快計(jì)算？這里有一個(gè)給你找點(diǎn)這個(gè)問(wèn)題的感覺(jué)的例子。給定一個(gè)大數(shù)Y,我們可以問(wèn)Y是否是復(fù)合數(shù)。例如，我們可能問(wèn)53308290611是否有非平凡的因子。回答是肯定的，雖然手工找出一個(gè)因子很麻煩。從另一個(gè)方面講，如果有人聲稱答案是"對(duì)，因?yàn)?24737可以整除53308290611",則我們可以很快用一個(gè)除法來(lái)驗(yàn)證。驗(yàn)證一個(gè)數(shù)是除數(shù)比首先找出除數(shù)來(lái)簡(jiǎn)單得多。用于驗(yàn)證一個(gè)正面答案所需的信息也稱為證書。所以我們的結(jié)論是，給定 正確的證書，問(wèn)題的正面答案可以很快的(也就是，在多項(xiàng)式時(shí)間內(nèi))驗(yàn)證，而這就是這個(gè)問(wèn)題屬于NP的原因。雖然這個(gè)特定的問(wèn)題，最近被證明為也在P類中(參看下面的關(guān)于"質(zhì)數(shù)在P中"的參考),這一點(diǎn)也不明顯，而且有很多類似的問(wèn)題相信不屬于類P。
限制到是/不是問(wèn)題并沒(méi)有改變問(wèn)題；即使我們?cè)试S更復(fù)雜的答案，最后的問(wèn)題(是否FP = FNP)是等價(jià)的。
