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

　　P對NP問(wen)題(ti)是(shi)克(ke)雷(lei)數(shu)學(xue)研(yan)究(jiu)所(suo)高(gao)額(e)懸(xuan)賞(shang)的(de)七(qi)個(ge)千(qian)禧(xi)年(nian)難(nan)題(ti)之(zhi)一(yi)，同(tong)時(shi)也(ye)是(shi)計(ji)算(suan)機(ji)科(ke)學(xue)領(ling)域(yu)的(de)最(zui)大(da)難(nan)題(ti)，關(guan)係(xi)到(dao)計(ji)算(suan)機(ji)完(wan)成(cheng)一(yi)項(xiang)任(ren)務(wu)的(de)速(su)度(du)到(dao)底(di)有(you)多(duo)快(kuai)。有(you)些(xie)問(wen)題(ti)計(ji)算(suan)起(qi)來(lai)很(hen)容(rong)易(yi)
，利(li)用(yong)多(duo)項(xiang)式(shi)算(suan)法(fa)很(hen)快(kuai)能(neng)解(jie)決(jue)，比(bi)如(ru)求(qiu)若(ruo)幹(gan)個(ge)數(shu)的(de)乘(cheng)積(ji)，這(zhe)類(lei)問(wen)題(ti)被(bei)稱(cheng)作(zuo)P問題；另一類問題計算過程比較繁瑣，但驗證答案卻很容易，比如把整數44427進行因數分解
，求解過程可能會很費時，但如果告訴你答案是177×251，簡單計算即可驗證答案是對的，這類問題就被歸為NP問題。

　　因此，如果P=NP
，那na麼me每mei個ge答da案an很hen容rong易yi得de到dao驗yan證zheng的de問wen題ti也ye同tong樣yang可ke以yi輕qing鬆song求qiu解jie。這zhe將jiang對dui計ji算suan機ji安an全quan構gou成cheng巨ju大da威wei脅xie，目mu前qian加jia密mi係xi統tong的de破po解jie就jiu相xiang當dang於yu要yao將jiang一yi個ge整zheng數shu分fen解jie為wei幾ji個ge因yin數shu的de乘cheng積ji，正zheng是shi其qi求qiu解jie過guo程cheng的de繁fan瑣suo
，才cai能neng杜du絕jue黑hei客ke的de入ru侵qin。

　　而現在
，迪奧拉裏卡圍繞一個眾所周知的NP問題進行論證，給出了P≠NP的答案。這就是布爾可滿足性問題（Boolean Satisfiability Problem）
，jixunwenyizuluojichenshushifounengtongshichenglihuozhehuxiangmaodun。diaolalikashengcheng
，tayijingzhengming，renhechengxudouwufaxunsujiedazhegewenti，yinci，tabushiyigeP問題。

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

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

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

　　    總編輯圈點

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

　　本篇文章來源於 科技網|www.stdaily.com

　　原文鏈接：http://www.stdaily.com/kjrb/content/2010-08/12/content_218335.htm

　　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包含所有那些可以由一個確定型圖靈機在多項式表達的時間內解決的問題

；類NPyousuoyouqikendingjiekeyizaigeidingzhengquexinxideduoxiangshishijianneiyanzhengdejuedingwentizucheng，huozhedengxiaodeshuo，naxiejiekeyizaifeiquedingtulingjishangzaiduoxiangshishijianneizhaochudewentidejihe。henkeneng，jisuanlilunzuidadeweijiejuewentijiushiguanyuzheliangleideguanxide:

　　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",則(ze)我(wo)們(men)可(ke)以(yi)很(hen)快(kuai)用(yong)一(yi)個(ge)除(chu)法(fa)來(lai)驗(yan)證(zheng)。驗(yan)證(zheng)一(yi)個(ge)數(shu)是(shi)除(chu)數(shu)比(bi)首(shou)先(xian)找(zhao)出(chu)除(chu)數(shu)來(lai)簡(jian)單(dan)得(de)多(duo)。用(yong)於(yu)驗(yan)證(zheng)一(yi)個(ge)正(zheng)麵(mian)答(da)案(an)所(suo)需(xu)的(de)信(xin)息(xi)也(ye)稱(cheng)為(wei)證(zheng)書(shu)。所(suo)以(yi)我(wo)們(men)的(de)結(jie)論(lun)是(shi)，給(gei)定(ding) 正確的證書，問題的正麵答案可以很快的(也就是，在多項式時間內)驗證
，而這就是這個問題屬於NP的原因。雖然這個特定的問題，最近被證明為也在P類中(參看下麵的關於"質數在P中"的參考),這一點也不明顯，而且有很多類似的問題相信不屬於類P。

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

　　形式化定義

　　更正式一些，一個決定問題是一個取一些字符串為輸入並要求輸出為是或否的問題。若有一個算法（譬如圖靈機
，或一個LISP或Pascal的程序並有無限的內存）能夠在最多nk步內對一個串長度為n的輸入給出正確答案
，其中k是某個不依賴於輸入串的常數，則我們稱該問題可以在多項式時間內解決

，並且將它置入類P。直觀的講，我們將P中的問題視為可以較快解決的問題。

　　現在假設有一個算法A(w,C)取兩個參數
，一個串w，也就是我們的決定問題的輸入串，而另一個串C是“建議證明”
，並且使得A在最多nk步之內產生“是/否”答案（其中n是w的長度而k不依賴於w）。進一步假設

　　w是一個答案為“是”的例子
，當且僅當
，存在C使得A(w,C)返回“是”。

　　則我們稱這個問題可以在非決定性多項式時間內解決
，且將它放入NP類。我們把算法A作為一個所建議的證明的檢驗器，它運行足夠快。（注意縮寫NP代表“Non-deterministic（非確定性）Polynomial（多項式）”而不是代表“Non-Polynomial（非多項式）。）

　　NP完全

　　要解決P = NP問題，NP完全的概念非常有用。不嚴格的講，NP完全問題是NP類中“最難”的問題，也就是說它們是最可能不屬於P類的。這是因為任何NP中的問題可以在多項式時間內變換成為任何特定NP完全問題的一個特例。例如
，旅行商問題的判定問題版本是NP完全的。所以NP中的任何問題的任何特例可以在多項式時間內機械地轉換成旅行商問題的一個特例。所以若旅行商問題被證明為在P內，則P = NP！旅行商問題是很多這樣的NP完全的問題之一。若任何一個NP完全的問題在P內，則可以推出P = NP。不幸的是，很多重要的問題被證明為NP完全，但沒有一個有已知快速的算法。

　　更難的問題

　　雖然是否P=NP還是未知的，在P之外的問題是已經知道存在的。尋找國際象棋或圍棋最佳走法（在n乘n棋盤上）是指數時間完全的。因為可以證明P ≠ EXPTIME（指數時間），這些問題位於P之外，所以需要比多項式時間更多的時間。判定Presburger算術中的命題是否為真的問題更加困難。Fischer和Rabin於1974年證明每個決定Presburger命題的真偽性的算法有最少2^(2^(cn))的運行時間，c為某個常數。這裏，n是Presburgermingtidechangdu。yinci，gaimingtiyizhixuyaobizhishushijiangengduodeyunxingshijian。bukepandingwentishigengjiakunnande，lirutingjiwenti。tamenwufazairenhegeidingshijianneijiejue。

　　P真的容易處理嗎？

　　上麵所有的討論假設了P表示“容易”而“不在P中”表示“困難”。這是一個在複雜度理論中常見而且有一定準確性的假設，它在實踐中卻不總是真的，原因包括如下幾點：

　　它忽略了常數因子。一個需要101000n時間的問題是屬於P的（它是線性時間的），但是事實上完全無法處理。一個需要10-100002n時間的問題不是在P中的（它是指數時間的），但是對於n 取值直到幾千時還是很容易處理的。

　　它忽略了指數的大小。一個時間複雜度n1000屬於P

，但是很難對付。已經證明在P中存在需要任意大的指數的問題（參看時間等級定理）。一個時間複雜度2n/1000的問題不屬於P，但對與n直到幾千還是容易應對的。

　　它隻考慮了最壞情況的複雜度。可能現實世界中的有些問題在多數時候可以在時間n中解決，但是很偶爾你會看到需要時間2n的特例。這個問題可能有一個多項式的平均時間，但最壞情況是指數式的
，所以該問題不屬於P。

　　它ta隻zhi考kao慮lv確que定ding性xing解jie。可ke能neng有you一yi個ge問wen題ti你ni可ke以yi很hen快kuai解jie決jue如ru果guo你ni可ke以yi接jie受shou出chu現xian一yi點dian誤wu差cha的de可ke能neng
，但dan是shi確que保bao正zheng確que的de答da案an會hui難nan得de多duo。這zhe個ge問wen題ti不bu會hui屬shu於yuP，雖然事實上它可以很快求解。這實際上是解決屬於NP而還不知道是否屬於P的問題的一個辦法（參看RP， BPP）。

　　新的諸如量子電腦這樣的計算模型，可能可以快速的解決一些尚未知道是否屬於P的問題；但是

，沒有一個它們已知能夠解決的問題是NP完全的。不過，必須注意到P和NP問題的定義是采用象圖靈機這樣的經典計算模型的屬於表述的。所以，即使一個量子計算機算法被發現能夠有效的解決一個NP完全問題，我們隻是有了一個快速解決困難問題的實際方法
，而不是數學類P和NP相等的證明。

　　計算機科學家為什麼認為P ≠ NP？

　　多數計算機科學家相信P≠NP。該信念的一個關鍵原因是經過數十年對這些問題的研究，沒有人能夠發現一個NP完全問題的多項式時間算法。而且，人們早在NP完全的概念出現前就開始尋求這些算法了（Karp的21個NP完全問題
，在最早發現的一批中，有所有著名的已經存在的問題]]）。進一步地，P = NP這樣的結果會導出很多驚人的結果，那些結果現在被相信是不成立的，例如NP = 餘NP和P = PH。

　　也有這樣論證的：問題較難求解(NP)但容易驗證(P)
，這和我們日常經驗是相符的。

　　從另一方麵講
，某些研究者認為我們過於相信P ≠ NP，而應該也去尋找P = NP的證明。例如
，2002年中有這樣的聲明：

　　傾向P≠NPdezhuyaolunjushizaiqiongjinsousuodelingyuwanquanmeiyoubenzhijinzhan。yejiushishuo
，yiwodeguandian，yigehenruodelunju。suanfadekongjianshihendade，erwomenzhishizaikaishitansuodeqidian。[ . . . ] 費馬最後定理的解決也顯示非常簡單的[sic]問題可能隻有用非常深刻的理論才能解決。

[page_break]
 

　　— Moshe Vardi，萊斯大學

　　過guo分fen依yi賴lai某mou種zhong投tou機ji不bu是shi規gui劃hua研yan究jiu的de一yi個ge好hao的de導dao引yin。我wo們men必bi須xu總zong是shi嚐chang試shi每mei個ge問wen題ti的de兩liang個ge方fang向xiang。偏pian見jian可ke能neng導dao致zhi著zhu名ming的de數shu學xue家jia無wu法fa解jie決jue答da案an和he他ta們men的de預yu計ji相xiang反fan的de著zhu名ming問wen題ti

，雖sui然ran他ta們men發fa展zhan了le所suo有you所suo需xu的de方fang法fa。

　　— Anil Nerode, 康奈爾大學

　　關於證明的難度的結果

　　雖(sui)然(ran)百(bai)萬(wan)美(mei)元(yuan)的(de)獎(jiang)金(jin)和(he)大(da)量(liang)投(tou)入(ru)巨(ju)大(da)卻(que)沒(mei)有(you)實(shi)質(zhi)性(xing)結(jie)果(guo)的(de)研(yan)究(jiu)足(zu)以(yi)顯(xian)示(shi)該(gai)問(wen)題(ti)是(shi)困(kun)難(nan)的(de)

，還(hai)有(you)一(yi)些(xie)形(xing)式(shi)化(hua)的(de)結(jie)果(guo)證(zheng)明(ming)為(wei)什(shen)麼(me)該(gai)問(wen)題(ti)可(ke)能(neng)很(hen)難(nan)解(jie)決(jue)。

　　最zui常chang被bei引yin用yong的de結jie果guo之zhi一yi設she計ji神shen喻yu。假jia想xiang你ni有you一yi個ge魔mo法fa機ji器qi可ke以yi解jie決jue單dan個ge問wen題ti，例li如ru決jue定ding一yi個ge給gei定ding的de數shu字zi是shi否fou為wei質zhi數shu
，但dan可ke以yi瞬shun間jian解jie決jue這zhe個ge問wen題ti。我wo們men的de新xin問wen題ti是shi，若ruo我wo們men被bei允yun許xu任ren意yi利li用yong這zhe個ge機ji器qi
，是shi否fou存cun在zai我wo們men可ke以yi在zai多duo項xiang式shi時shi間jian內nei驗yan證zheng但dan無wu法fa在zai多duo項xiang式shi時shi間jian內nei解jie決jue的de問wen題ti
？結jie果guo是shi，依yi賴lai於yu機ji器qi能neng解jie決jue的de問wen題ti
，P = NP和P ≠ NPerzhedoukeyizhengming。zhegejielundehouguoshi
，renhekeyixiugailaizhengminggaijiqidecunzaixingdejieguobunengjiejuewenti。buxingdeshi
，jihusuoyoujingdiandefangfahedabufenyizhidefangfakeyizheyangxiugai（我們稱它們在相對化）。

　　如果這還不算太糟的話，1993年Razborov和Rudich證明的一個結果表明，給定一個特定的可信的假設，在某種意義下“自然”的證明不能解決P = NP問題。[3] 這表明一些現在似乎最有希望的方法不太可能成功。隨著更多這類的定理得到證明，該定理的可能證明有越來越多的陷阱要規避。

　　這實際上也是為什麼NP完全問題有用的原因：若有一個多項式時間算法，或者沒有一個這樣的算法
，對於NP完全問題存在，這將用一種相信不被上述結果排除在外的方法來解決P = NP問題。

　　多項式時間算法

　　沒人知道多項式時間算法對於NP完全問題是否存在。但是如果這樣的算法存在，我們已經知道其中的一些了！例如，下麵的算法正確的接受了一個NP完全語言，但是沒人知道通常它需要多久運行。它是一個多項式時間算法當且僅當P = NP。

　　// 接受NP完全語言的一個算法子集和。

　　//

　　// 這是一個多項式時間算法當且僅當P=NP。

　　//

　　// “多項式時間”表示它在多項式時間內返回“是”，若

　　// 結果是“是”，否則永遠運行。

　　//

　　// 輸入：S = 一個自然數的有限集

　　// 輸出："是" 如果某個S的子集加起來等於0。

　　// 否則，它永遠運行沒有輸出。

　　// 注意: "程序數P" 是你將一個整數P寫為二進製

，然後

　　// 將位串考慮為一個程序。

　　// 每個可能的程序都可以這樣產生
，

　　// 雖然多數什麼也不做因為有語法錯誤。

　　//

　　FOR N = 1...infinity

　　FOR P = 1...N

　　以S為輸入運行程序數P N步

　　IF 程序輸出一個不同的整數的列表

　　AND 所有整數都在S中

　　AND 整數的和為0

　　THEN

　　OUTPUT "是" 並 停機

　　若P = NP

，則這是一個接受一個NP完全語言的多項式時間算法。“接受”表示它在多項式時間內給出“是”的答案，但允許在答案是“否”的時候永遠運行。

　　可能我們想要“解決”子集和問題，而不是僅僅“接受”子集和語言。這表示我們想要它總是停機並返回一個“是”或“否”dedaan。shifoucunzairenhekenengzaiduoxiangshishijianneijiejuezhegewentidesuanfa？meiyourenzhidao。danshiruguozheyangdesuanfacunzai，namewomenyijingzhidaoqizhongdeyixiele！隻要將上麵的算法中的IF語句替換成下麵的語句：

　　IF 程序輸出一個完整的數學證明

　　AND 證明的每一步合法

　　AND 結論是S確實有（或者沒有）一個和為0的子集

　　THEN

　　OUTPUT "是" （或者"不是"如果那被證明了）並停機

　　邏輯表述

　　P=NP問題可以用邏輯命題的特定類的可表達性的術語來重新表述。所有P中的語言可以用一階邏輯加上最小不動點操作（實際上，這允許了遞歸函數的定義）來表達。類似地，NP是可以用存在性二階邏輯來表達—也就是，在關係
、函數、和子集上排除了全域量詞的二階邏輯。多項式等級
，PH中的語言對應與所有的二階邏輯。這樣，“P是NP的真子集嗎”這樣的問題可以表述為“是否存在性二階邏輯能夠表達帶最小不動點操作的一階邏輯的所不能表達的語言？”

　　花絮

　　普林斯頓大學計算機係樓將二進製代碼表述的“P=NP?”問題刻進頂樓西麵的磚頭上。如果證明了P=NP，磚頭可以很方便的換成表示“P=NP！”。[4]

　　康奈爾大學的Hubert Chen博士提供了這個玩笑式的P不等於NP的證明：“反證法。設P = NP。令y為一個P = NP的證明。證明y可以用一個合格的計算機科學家在多項式時間內驗證
，我們認定這樣的科學家的存在性為真。但是
，因為P = NP，該證明y可以在多項式時間內由這樣的科學家發現。但是這樣的發現還沒有發生（雖然這樣的科學家試圖發現這樣的一個證明）
，我們得到矛盾。

　　最新消息

　　HP LAB的 Vinay Deolalikar 教授宣布於公元2010年8月6日證明了P!=NP，證明文章[1]已經發送到該問題各相關領域專家手中
，等待檢驗。在他的主頁上，證明過程已經公布（PDF格式共103頁）。

　　參考資料

　　• 1.

　　Vinay Deolalikar 教授主頁

　　http://www.hpl.hp.com/personal/Vinay_Deolalikar/