999国内精品永久免费视频,色偷偷9999www,亚洲国产成人爱av在线播放,6080亚洲人久久精品,欧美超高清xxxhd

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

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

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

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

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

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

　　迪奧拉里卡的論文草稿已經(jīng)得到了復(fù)雜性理論家的認(rèn)可，但一周后公布的論文終稿還將接受嚴(yán)格的審查。

　　    總編輯圈點(diǎn)

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

　　本篇文章來源于 科技網(wǎng)|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問題是在理論信息學(xué)中計(jì)算復(fù)雜度理論領(lǐng)域里至今沒有解決的問題，它被“克雷數(shù)學(xué)研究所”（Clay Mathematics Institute, 簡(jiǎn)稱CMI）在千禧年大獎(jiǎng)難題中收錄。P/NP問題中包含了復(fù)雜度類P與NP的關(guān)系。1971年史提芬•古克(Stephen A. Cook) 和 Leonid Levin 相對(duì)獨(dú)立的提出了下面的問題,即是否兩個(gè)復(fù)雜度類P和NP是恒等的（P=NP?）。

　　P和NP

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

　　P和NP相等嗎?

　　在2002年對(duì)于100研究者的調(diào)查，61人相信答案是否定的，9個(gè)相信答案是肯定的，22個(gè)不確定，而8個(gè)相信該問題可能和現(xiàn)在所接受的公理獨(dú)立，所以不可能證明或證否。[1] 對(duì)于正確的解答，有一個(gè)1,000,000美元的獎(jiǎng)勵(lì)。

　　NP-完全問題(或者叫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問題問道：如果是/不是問題的正面答案可以很快驗(yàn)證，其答案是否也可以很快計(jì)算？這里有一個(gè)給你找點(diǎn)這個(gè)問題的感覺的例子。給定一個(gè)大數(shù)Y,我們可以問Y是否是復(fù)合數(shù)。例如，我們可能問53308290611是否有非平凡的因子。回答是肯定的，雖然手工找出一個(gè)因子很麻煩。從另一個(gè)方面講，如果有人聲稱答案是"對(duì)，因?yàn)?24737可以整除53308290611",則我們可以很快用一個(gè)除法來驗(yàn)證。驗(yàn)證一個(gè)數(shù)是除數(shù)比首先找出除數(shù)來簡(jiǎn)單得多。用于驗(yàn)證一個(gè)正面答案所需的信息也稱為證書。所以我們的結(jié)論是，給定 正確的證書，問題的正面答案可以很快的(也就是，在多項(xiàng)式時(shí)間內(nèi))驗(yàn)證，而這就是這個(gè)問題屬于NP的原因。雖然這個(gè)特定的問題，最近被證明為也在P類中(參看下面的關(guān)于"質(zhì)數(shù)在P中"的參考),這一點(diǎn)也不明顯，而且有很多類似的問題相信不屬于類P。

　　限制到是/不是問題并沒有改變問題；即使我們?cè)试S更復(fù)雜的答案，最后的問題(是否FP = FNP)是等價(jià)的。

　　形式化定義

　　更正式一些，一個(gè)決定問題是一個(gè)取一些字符串為輸入并要求輸出為是或否的問題。若有一個(gè)算法（譬如圖靈機(jī)，或一個(gè)LISP或Pascal的程序并有無限的內(nèi)存）能夠在最多nk步內(nèi)對(duì)一個(gè)串長(zhǎng)度為n的輸入給出正確答案，其中k是某個(gè)不依賴于輸入串的常數(shù)，則我們稱該問題可以在多項(xiàng)式時(shí)間內(nèi)解決，并且將它置入類P。直觀的講，我們將P中的問題視為可以較快解決的問題。

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

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

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

　　NP完全

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

　　更難的問題

　　雖然是否P=NP還是未知的，在P之外的問題是已經(jīng)知道存在的。尋找國(guó)際象棋或圍棋最佳走法（在n乘n棋盤上）是指數(shù)時(shí)間完全的。因?yàn)榭梢宰C明P ≠ EXPTIME（指數(shù)時(shí)間），這些問題位于P之外，所以需要比多項(xiàng)式時(shí)間更多的時(shí)間。判定Presburger算術(shù)中的命題是否為真的問題更加困難。Fischer和Rabin于1974年證明每個(gè)決定Presburger命題的真?zhèn)涡缘乃惴ㄓ凶钌?^(2^(cn))的運(yùn)行時(shí)間，c為某個(gè)常數(shù)。這里，n是Presburger命題的長(zhǎng)度。因此，該命題已知需要比指數(shù)時(shí)間更多的運(yùn)行時(shí)間。不可判定問題是更加困難的，例如停機(jī)問題。它們無法在任何給定時(shí)間內(nèi)解決。

　　P真的容易處理嗎？

　　上面所有的討論假設(shè)了P表示“容易”而“不在P中”表示“困難”。這是一個(gè)在復(fù)雜度理論中常見而且有一定準(zhǔn)確性的假設(shè)，它在實(shí)踐中卻不總是真的，原因包括如下幾點(diǎn)：

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

　　它忽略了指數(shù)的大小。一個(gè)時(shí)間復(fù)雜度n1000屬于P，但是很難對(duì)付。已經(jīng)證明在P中存在需要任意大的指數(shù)的問題（參看時(shí)間等級(jí)定理）。一個(gè)時(shí)間復(fù)雜度2n/1000的問題不屬于P，但對(duì)與n直到幾千還是容易應(yīng)對(duì)的。

　　它只考慮了最壞情況的復(fù)雜度。可能現(xiàn)實(shí)世界中的有些問題在多數(shù)時(shí)候可以在時(shí)間n中解決，但是很偶爾你會(huì)看到需要時(shí)間2n的特例。這個(gè)問題可能有一個(gè)多項(xiàng)式的平均時(shí)間，但最壞情況是指數(shù)式的，所以該問題不屬于P。

　　它只考慮確定性解?？赡苡幸粋€(gè)問題你可以很快解決如果你可以接受出現(xiàn)一點(diǎn)誤差的可能，但是確保正確的答案會(huì)難得多。這個(gè)問題不會(huì)屬于P，雖然事實(shí)上它可以很快求解。這實(shí)際上是解決屬于NP而還不知道是否屬于P的問題的一個(gè)辦法（參看RP， BPP）。

　　新的諸如量子電腦這樣的計(jì)算模型，可能可以快速的解決一些尚未知道是否屬于P的問題；但是，沒有一個(gè)它們已知能夠解決的問題是NP完全的。不過，必須注意到P和NP問題的定義是采用象圖靈機(jī)這樣的經(jīng)典計(jì)算模型的屬于表述的。所以，即使一個(gè)量子計(jì)算機(jī)算法被發(fā)現(xiàn)能夠有效的解決一個(gè)NP完全問題，我們只是有了一個(gè)快速解決困難問題的實(shí)際方法，而不是數(shù)學(xué)類P和NP相等的證明。

　　計(jì)算機(jī)科學(xué)家為什么認(rèn)為P ≠ NP？

　　多數(shù)計(jì)算機(jī)科學(xué)家相信P≠NP。該信念的一個(gè)關(guān)鍵原因是經(jīng)過數(shù)十年對(duì)這些問題的研究，沒有人能夠發(fā)現(xiàn)一個(gè)NP完全問題的多項(xiàng)式時(shí)間算法。而且，人們?cè)缭贜P完全的概念出現(xiàn)前就開始尋求這些算法了（Karp的21個(gè)NP完全問題，在最早發(fā)現(xiàn)的一批中，有所有著名的已經(jīng)存在的問題]]）。進(jìn)一步地，P = NP這樣的結(jié)果會(huì)導(dǎo)出很多驚人的結(jié)果，那些結(jié)果現(xiàn)在被相信是不成立的，例如NP = 余NP和P = PH。

　　也有這樣論證的：?jiǎn)栴}較難求解(NP)但容易驗(yàn)證(P)，這和我們?nèi)粘＝?jīng)驗(yàn)是相符的。

　　從另一方面講，某些研究者認(rèn)為我們過于相信P ≠ NP，而應(yīng)該也去尋找P = NP的證明。例如，2002年中有這樣的聲明：

　　傾向P≠NP的主要論據(jù)是在窮盡搜索的領(lǐng)域完全沒有本質(zhì)進(jìn)展。也就是說，以我的觀點(diǎn)，一個(gè)很弱的論據(jù)。算法的空間是很大的，而我們只是在開始探索的起點(diǎn)。[ . . . ] 費(fèi)馬最後定理的解決也顯示非常簡(jiǎn)單的[sic]問題可能只有用非常深刻的理論才能解決。

[page_break]
 

　　— Moshe Vardi，萊斯大學(xué)

　　過分依賴某種投機(jī)不是規(guī)劃研究的一個(gè)好的導(dǎo)引。我們必須總是嘗試每個(gè)問題的兩個(gè)方向。偏見可能導(dǎo)致著名的數(shù)學(xué)家無法解決答案和他們的預(yù)計(jì)相反的著名問題，雖然他們發(fā)展了所有所需的方法。

　　— Anil Nerode, 康奈爾大學(xué)

　　關(guān)于證明的難度的結(jié)果

　　雖然百萬美元的獎(jiǎng)金和大量投入巨大卻沒有實(shí)質(zhì)性結(jié)果的研究足以顯示該問題是困難的，還有一些形式化的結(jié)果證明為什么該問題可能很難解決。

　　最常被引用的結(jié)果之一設(shè)計(jì)神喻。假想你有一個(gè)魔法機(jī)器可以解決單個(gè)問題，例如決定一個(gè)給定的數(shù)字是否為質(zhì)數(shù)，但可以瞬間解決這個(gè)問題。我們的新問題是，若我們被允許任意利用這個(gè)機(jī)器，是否存在我們可以在多項(xiàng)式時(shí)間內(nèi)驗(yàn)證但無法在多項(xiàng)式時(shí)間內(nèi)解決的問題？結(jié)果是，依賴于機(jī)器能解決的問題，P = NP和P ≠ NP二者都可以證明。這個(gè)結(jié)論的后果是，任何可以修改來證明該機(jī)器的存在性的結(jié)果不能解決問題。不幸的是，幾乎所有經(jīng)典的方法和大部分已知的方法可以這樣修改（我們稱它們?cè)谙鄬?duì)化）。

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

　　這實(shí)際上也是為什么NP完全問題有用的原因：若有一個(gè)多項(xiàng)式時(shí)間算法，或者沒有一個(gè)這樣的算法，對(duì)于NP完全問題存在，這將用一種相信不被上述結(jié)果排除在外的方法來解決P = NP問題。

　　多項(xiàng)式時(shí)間算法

　　沒人知道多項(xiàng)式時(shí)間算法對(duì)于NP完全問題是否存在。但是如果這樣的算法存在，我們已經(jīng)知道其中的一些了！例如，下面的算法正確的接受了一個(gè)NP完全語言，但是沒人知道通常它需要多久運(yùn)行。它是一個(gè)多項(xiàng)式時(shí)間算法當(dāng)且僅當(dāng)P = NP。

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

　　//

　　// 這是一個(gè)多項(xiàng)式時(shí)間算法當(dāng)且僅當(dāng)P=NP。

　　//

　　// “多項(xiàng)式時(shí)間”表示它在多項(xiàng)式時(shí)間內(nèi)返回“是”，若

　　// 結(jié)果是“是”，否則永遠(yuǎn)運(yùn)行。

　　//

　　// 輸入：S = 一個(gè)自然數(shù)的有限集

　　// 輸出："是" 如果某個(gè)S的子集加起來等于0。

　　// 否則，它永遠(yuǎn)運(yùn)行沒有輸出。

　　// 注意: "程序數(shù)P" 是你將一個(gè)整數(shù)P寫為二進(jìn)制，然后

　　// 將位串考慮為一個(gè)程序。

　　// 每個(gè)可能的程序都可以這樣產(chǎn)生，

　　// 雖然多數(shù)什么也不做因?yàn)橛姓Z法錯(cuò)誤。

　　//

　　FOR N = 1...infinity

　　FOR P = 1...N

　　以S為輸入運(yùn)行程序數(shù)P N步

　　IF 程序輸出一個(gè)不同的整數(shù)的列表

　　AND 所有整數(shù)都在S中

　　AND 整數(shù)的和為0

　　THEN

　　OUTPUT "是" 并 停機(jī)

　　若P = NP，則這是一個(gè)接受一個(gè)NP完全語言的多項(xiàng)式時(shí)間算法。“接受”表示它在多項(xiàng)式時(shí)間內(nèi)給出“是”的答案，但允許在答案是“否”的時(shí)候永遠(yuǎn)運(yùn)行。

　　可能我們想要“解決”子集和問題，而不是僅僅“接受”子集和語言。這表示我們想要它總是停機(jī)并返回一個(gè)“是”或“否”的答案。是否存在任何可能在多項(xiàng)式時(shí)間內(nèi)解決這個(gè)問題的算法？沒有人知道。但是如果這樣的算法存在，那么我們已經(jīng)知道其中的一些了！只要將上面的算法中的IF語句替換成下面的語句：

　　IF 程序輸出一個(gè)完整的數(shù)學(xué)證明

　　AND 證明的每一步合法

　　AND 結(jié)論是S確實(shí)有（或者沒有）一個(gè)和為0的子集

　　THEN

　　OUTPUT "是" （或者"不是"如果那被證明了）并停機(jī)

　　邏輯表述

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

　　花絮

　　普林斯頓大學(xué)計(jì)算機(jī)系樓將二進(jìn)制代碼表述的“P=NP?”問題刻進(jìn)頂樓西面的磚頭上。如果證明了P=NP，磚頭可以很方便的換成表示“P=NP！”。[4]

　　康奈爾大學(xué)的Hubert Chen博士提供了這個(gè)玩笑式的P不等于NP的證明：“反證法。設(shè)P = NP。令y為一個(gè)P = NP的證明。證明y可以用一個(gè)合格的計(jì)算機(jī)科學(xué)家在多項(xiàng)式時(shí)間內(nèi)驗(yàn)證，我們認(rèn)定這樣的科學(xué)家的存在性為真。但是，因?yàn)镻 = NP，該證明y可以在多項(xiàng)式時(shí)間內(nèi)由這樣的科學(xué)家發(fā)現(xiàn)。但是這樣的發(fā)現(xiàn)還沒有發(fā)生（雖然這樣的科學(xué)家試圖發(fā)現(xiàn)這樣的一個(gè)證明），我們得到矛盾。

　　最新消息

　　HP LAB的 Vinay Deolalikar 教授宣布于公元2010年8月6日證明了P!=NP，證明文章[1]已經(jīng)發(fā)送到該問題各相關(guān)領(lǐng)域?qū)＜沂种?，等待檢驗(yàn)。在他的主頁(yè)上，證明過程已經(jīng)公布（PDF格式共103頁(yè)）。

　　參考資料

　　• 1.

　　Vinay Deolalikar 教授主頁(yè)

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