P-NP-NPC三者問題闡述.doc

P NP NPC三者問題闡述1）P對(duì)NP問題是什么意思?首先說明一下問題的復(fù)雜性和算法的復(fù)雜性的區(qū)別，下面只考慮時(shí)間復(fù)雜性。算法的復(fù)雜性是指解決問題的一個(gè)具體的算法的執(zhí)行時(shí)間，這是算法的性質(zhì)；問題的復(fù)雜性是指這個(gè)問題本身的復(fù)雜程度，是問題的性質(zhì)。比如對(duì)于排序問題，如果我們只能通過元素間的相互比較來確定元素間的相互位置，而沒有其他的附加可用信息，則排序問題的復(fù)雜性是O(nlgn)，但是排序算法有很多，冒泡法是O(n2)，快速排序平均情況下是O(nlgn)等等，排序問題的復(fù)雜性是指在所有的解決該問題的算法中最好算法的復(fù)雜性。問題的復(fù)雜性不可能通過枚舉各種可能算法來得到，一般都是預(yù)先估計(jì)一個(gè)值，然后從理論上證明。為了研究問題的復(fù)雜性，我們必須將問題抽象，為了簡(jiǎn)化問題，我們只考慮一類簡(jiǎn)單的問題，判定性問題，即提出一個(gè)問題，只需要回答yes或者no的問題。任何一般的最優(yōu)化問題都可以轉(zhuǎn)化為一系列判定性問題，比如求圖中從A到B的最短路徑，可以轉(zhuǎn)化成：從A到B是否有長(zhǎng)度為1的路徑？從A到B是否有長(zhǎng)度為2的路徑？從A到B是否有長(zhǎng)度為k的路徑？如果問到了k的時(shí)候回答了yes，則停止發(fā)問，我們可以說從A到B的最短路徑就是k。如果一個(gè)判定性問題的復(fù)雜度是該問題的一個(gè)實(shí)例的規(guī)模n的多項(xiàng)式函數(shù)，則我們說這種可以在多項(xiàng)式時(shí)間內(nèi)解決的判定性問題屬于P類問題。P類問題就是所有復(fù)雜度為多項(xiàng)式時(shí)間的問題的集合。然而有些問題很難找到多項(xiàng)式時(shí)間的算法（或許根本不存在），比如找出無向圖中的哈米爾頓回路問題，但是我們發(fā)現(xiàn)如果給了我們?cè)搯栴}的一個(gè)答案，我們可以在多項(xiàng)式時(shí)間內(nèi)判斷這個(gè)答案是否正確。比如說對(duì)于哈米爾頓回路問題，給一個(gè)任意的回路，我們很容易判斷他是否是哈米爾頓回路（只要看是不是所有的頂點(diǎn)都在回路中就可以了）。這種可以在多項(xiàng)式時(shí)間內(nèi)驗(yàn)證一個(gè)解是否正確的問題稱為NP問題。顯然，所有的P類問題都是屬于NP問題的，但是現(xiàn)在的問題是，P是否等于NP?這個(gè)問題至今還未解決。注意，NP問題不一定都是難解的問題，比如簡(jiǎn)單的數(shù)組排序問題是P類問題，但是P屬于NP，所以也是NP問題，你能說他很難解么？剛才說了，現(xiàn)在還不知道是否有P=NP或者PNP，但是后來人們發(fā)現(xiàn)還有一系列的特殊NP問題，這類問題的特殊性質(zhì)使得很多人相信PNP，只不過現(xiàn)在還無法證明。這類特殊的NP問題就是NP完全問題（NPC問題，C代表complete）。NPC問題存在著一個(gè)令人驚訝的性質(zhì)，即如果一個(gè)NPC問題存在多項(xiàng)式時(shí)間的算法，則所有的NP問題都可以在多項(xiàng)式時(shí)間內(nèi)求解，即P=NP成立！這是因?yàn)?，每一個(gè)NPC問題可以在多項(xiàng)式時(shí)間內(nèi)轉(zhuǎn)化成任何一個(gè)NP問題。比如前面說的哈米爾頓回路問題就是一個(gè)NPC問題。NPC問題的歷史并不久，cook在1971年找到了第一個(gè)NPC問題，此后人們又陸續(xù)發(fā)現(xiàn)很多NPC問題，現(xiàn)在可能已經(jīng)有3000多個(gè)了。所以，我們一般認(rèn)為NPC問題是難解的問題，因?yàn)樗惶赡艽嬖谝粋€(gè)多項(xiàng)式時(shí)間的算法（如果存在則所有的NP問題都存在多項(xiàng)式時(shí)間算法，這太不可思議了，但是也不是不可能）。類似哈米爾頓回路/路徑問題，旅行商問題，集團(tuán)問題，最小邊覆蓋問題（注意和路徑覆蓋的區(qū)別），等等很多問題都是NPC問題，所以都是難解的問題。2）淺談np問題NP完全問題在科學(xué)研究和實(shí)際應(yīng)用中廣泛存在，僅僅指出它們的難解性是不夠的，更重要的是正面尋求解決方法，其中的關(guān)鍵是算法的設(shè)計(jì)與分析。 圖靈機(jī) 寬泛地講，圖靈機(jī)可以說是一個(gè)復(fù)雜的代數(shù)結(jié)構(gòu)，它又是一個(gè)通用的計(jì)算機(jī)模型，能做計(jì)算機(jī)可以做的所有事情。當(dāng)然，圖靈機(jī)也有不能解決的問題，但這些問題事實(shí)已經(jīng)超出了計(jì)算機(jī)的能力范圍了，我們現(xiàn)在基本上是這樣認(rèn)為的。 費(fèi)馬大定理 17世紀(jì)的一位法國(guó)數(shù)學(xué)家，提出了一個(gè)數(shù)學(xué)難題，使得后來的數(shù)學(xué)家一籌莫展，這個(gè)人就是費(fèi)馬。 這道題是這樣的:當(dāng)n2時(shí)，xn+yn=zn沒有正整數(shù)解，在數(shù)學(xué)上被稱為“費(fèi)馬大定理”。為了獲得它的一個(gè)肯定的或者否定的證明，歷史上幾次懸賞征求答案，一代又一代最優(yōu)秀的數(shù)學(xué)家都曾研究過，但是300多年過去了，至今既未獲得最終證明，也未被推翻。即使用現(xiàn)代的電子計(jì)算機(jī)也只能證明:當(dāng)n小于等于4100萬時(shí)，費(fèi)馬大定理是正確的。由于當(dāng)時(shí)費(fèi)馬聲稱他已解決了這個(gè)問題，但是他沒有公布結(jié)果，于是留下數(shù)學(xué)難題中少有的千古之謎。 有數(shù)學(xué)家說過“一個(gè)好的問題勝過十個(gè)好解答”。因?yàn)榻獯鹨怀?，此問題已是到了終點(diǎn)，對(duì)不斷求創(chuàng)新的人們而言，已不構(gòu)成挑戰(zhàn)。而新的問題是源頭活水，能開拓新的境界。多數(shù)人都不愿沉醉在好的解答中不斷地玩味，而希望找到新的問題，不斷地思考、摸索。 了解NP問題 “P=NP？”這個(gè)問題，作為理論計(jì)算機(jī)科學(xué)的核心問題，其聲名早已經(jīng)超越了這個(gè)領(lǐng)域。它是Clay研究所的七個(gè)百萬美元大獎(jiǎng)問題之一，在2006國(guó)際數(shù)學(xué)家大會(huì)上，它是某個(gè)1小時(shí)講座的主題。 要說起P和NP是什么東西，得先從算法的多項(xiàng)式時(shí)間復(fù)雜度談起，注意，這里面的兩個(gè)P都是指Polynomial（多項(xiàng)式）。 一個(gè)問題的規(guī)模指的是輸入的總位數(shù)，比如一個(gè)n個(gè)數(shù)的排序問題，輸入規(guī)模就是n。在某些時(shí)候，輸入規(guī)模是值得注意的，比如判定一個(gè)數(shù)n是否是一個(gè)質(zhì)數(shù)這個(gè)問題，它的輸入規(guī)模并不是n，而是log(n)，因?yàn)橐粋€(gè)數(shù)n用大約log(n)位就能表示出來了，這也是為何枚舉因子判定素?cái)?shù)的算法并不是多項(xiàng)式時(shí)間算法的原因。 如果一個(gè)算法，能在以輸入規(guī)模為參變量的某個(gè)多項(xiàng)式的時(shí)間內(nèi)給出答案，則稱它為多項(xiàng)式時(shí)間算法。注意:這里的多項(xiàng)式時(shí)間是指算法運(yùn)行的步數(shù)。一個(gè)算法是否是多項(xiàng)式算法，與計(jì)算模型的具體的物理實(shí)現(xiàn)沒有關(guān)系，雖然大多數(shù)假想的計(jì)算模型不可能有任何物理的實(shí)現(xiàn)。 P指確定型圖靈機(jī)上的具有多項(xiàng)式算法的問題集合，NP指非確定型圖靈機(jī)上具有多項(xiàng)式算法的問題集合，這里N是不確定的意思。 脫離圖靈機(jī)的概念，就在普通的計(jì)算機(jī)上看，P問題是指能夠在多項(xiàng)式時(shí)間求解的判定問題（判定問題指只需要回答是和不是的問題），而NP問題則是指那些其肯定解能夠在給定正確信息下在多項(xiàng)式時(shí)間內(nèi)驗(yàn)證的判定問題。比如，要判定一個(gè)數(shù)是合數(shù)，如果給我一個(gè)約數(shù)，我們就很快判定它就是合數(shù)。所以判定一個(gè)數(shù)是合數(shù)的問題屬于NP。 NP問題的代表問題之一是售貨員旅行問題(traveling salesman problem)。有一個(gè)售貨員要 汽車到n個(gè)指定的城市去推銷貨物，他必須經(jīng)過全部的n個(gè)城市?，F(xiàn)在他有此n城的地圖及各城之間的公路距離，試問他應(yīng)如何取最短的行程從家中出發(fā)再回到家中。 NP問題的歷史 人們?cè)谄呤甏_始對(duì)NP完全問題的研究主要是橫向發(fā)展，也就是以許多不同的計(jì)算模型來分析難解問題的本質(zhì)。這些新的計(jì)算模型包括了平行計(jì)算模型、概率計(jì)算模型、布爾線路、判斷樹、平均復(fù)雜性、交互證明系統(tǒng)以及程式長(zhǎng)度復(fù)雜性等等。對(duì)這些新的計(jì)算模型的研究一方面使我們對(duì)難解問題有了更深一層的認(rèn)識(shí)，一方面也產(chǎn)生了一些預(yù)想不到的應(yīng)用。最顯著的一個(gè)例子就是計(jì)算密碼學(xué)的革命性突破：基于NP問題的公鑰密碼體系。另一個(gè)有名的例子是線性規(guī)劃的多項(xiàng)式時(shí)間解的發(fā)現(xiàn)。 到了八十年代中，對(duì)NP完全問題的研究有了縱向的突破，在許多表面看來并不相關(guān)的計(jì)算模型之間發(fā)現(xiàn)了深刻的刻劃關(guān)系。這些刻劃關(guān)系不但解決了幾個(gè)令人困擾多年的未解問題，同時(shí)也刺激了其它相關(guān)領(lǐng)域的發(fā)展。其中之一是對(duì)線路復(fù)雜性的研究發(fā)現(xiàn)了一些問題在某種有限制的線路模型中必有指數(shù)下界。這些結(jié)果使用了組合數(shù)學(xué)與概率方法等新的數(shù)學(xué)工具，并且解決了一個(gè)有名的有關(guān)多項(xiàng)式分層的未解問題。另一個(gè)更重大的結(jié)果是以概率可驗(yàn)證明對(duì)NP類的刻劃。這個(gè)結(jié)果來自于對(duì)交互證明系統(tǒng)這個(gè)概念的擴(kuò)展，并且使用了線性代數(shù)與編碼理論等數(shù)學(xué)證明技巧。 但是，明顯的，目前還沒有一個(gè)看上去有希望的方向。 數(shù)學(xué)里最偉大的定理之一費(fèi)馬大定理，用了數(shù)學(xué)家紛紛發(fā)表了300多年時(shí)光。NP問題，作為理論計(jì)算機(jī)領(lǐng)域最困難的問題，40年時(shí)間似乎太短了。 大師的看法 對(duì)于NP是否等于P，大家看法不一。在2002年對(duì)于100個(gè)研究者的調(diào)查中，61人相信答案是否定的，9個(gè)相信答案是肯定的，22個(gè)不確定，而8個(gè)相信該問題可能和現(xiàn)在所接受的公理獨(dú)立，所以不可能證明或證否。 在這份調(diào)查報(bào)告中，國(guó)際上著名的計(jì)算機(jī)學(xué)家對(duì)這個(gè)問題的看法。 Avi Wigderson:(美國(guó)普林斯頓高等研究院教授)我想這個(gè)項(xiàng)目還沒有成熟，因?yàn)殛P(guān)于這個(gè)項(xiàng)目的相關(guān)知識(shí)我們了解的太少了。我唯一可以確定的事情就是，人類所有提出的問題中最重要和最有趣的問題之一，是越來越多的人和資源應(yīng)該參與其中，才能得到更好的猜想結(jié)果。 姚期智:（清華大學(xué)教授）很難說何時(shí)能夠解決這個(gè)問題。我的猜想還沒有得到學(xué)術(shù)界的驗(yàn)證，結(jié)果很可能是P問題并不等于NP問題，我認(rèn)為使用數(shù)學(xué)技術(shù)會(huì)非常完美的。 可能的結(jié)果 從實(shí)際應(yīng)用來說，人們都希望NP=P，因?yàn)檫@意味著很多問題都能有有效的算法，但有些極為詭異的結(jié)果也是可能的，人們從這個(gè)結(jié)果中什么都得不到。 比如某一天人們最終使用某種數(shù)學(xué)上的技巧證明了NP問題的多項(xiàng)式時(shí)間算法的存在性，但并不知道如何找到它這在數(shù)學(xué)上是極為可能的，那最終會(huì)怎么樣呢？ 這種情況不會(huì)發(fā)生，事實(shí)上，在NP=P的假設(shè)下，人們已經(jīng)找到了NP完全問題的多項(xiàng)法解法，但這并沒有好太多，如果NP=P，很多算法便是一個(gè)NP完全問題的多項(xiàng)式時(shí)間算法?？墒撬稽c(diǎn)價(jià)值都沒有，更不用說來解決實(shí)際問題了。 經(jīng)典計(jì)算中存在著一大類NP 問題。這類問題在經(jīng)典計(jì)算機(jī)上是不能計(jì)算的，但是量子計(jì)算可以把其中的一部分NP問題變成 P問題，即問題的復(fù)雜度隨著比特位數(shù)的增長(zhǎng)以多項(xiàng)式數(shù)量級(jí)上升。這類問題原則上是可以計(jì)算的。 一個(gè)具體的例子就是大因數(shù)分解，按經(jīng)典計(jì)算復(fù)雜性理論，這個(gè)問題不存在有效算法。但是如果用量子計(jì)算機(jī)結(jié)合Shor量子算法，這個(gè)問題就變成了P問題。 現(xiàn)狀 P和NP是理論計(jì)算機(jī)科學(xué)的核心問題。從數(shù)學(xué)的角度來說，它和其他歷史上有名的數(shù)學(xué)問題一樣，給與人們一個(gè)智力上重大的挑戰(zhàn)。而更為重要的是，在無數(shù)與計(jì)算有關(guān)的的學(xué)術(shù)領(lǐng)域中，NP完全問題以各種不同形式層出不窮。因此，這并不是一個(gè)純粹的與世獨(dú)立的智力游戲，而是對(duì)計(jì)算機(jī)科學(xué)有全面影響力的問題。 計(jì)算機(jī)與社會(huì)科學(xué)、自然科學(xué)和思維科學(xué)等許多學(xué)科相互滲透和交叉，形成了許多新的邊緣學(xué)科和新學(xué)科群，正在改變?cè)S多傳統(tǒng)學(xué)科。分子與量子計(jì)算機(jī)的深入研究和技術(shù)難關(guān)的攻克，并最終投入運(yùn)算，必將在政治、經(jīng)濟(jì)、軍事、文化乃至人類生活的各個(gè)方面產(chǎn)生深刻的影響。 最近美國(guó)南加州大學(xué)Adleman博士應(yīng)用基于DNA分子計(jì)算技術(shù)的生物實(shí)驗(yàn)方法有效地求解了“哈密頓路徑問題”目前計(jì)算機(jī)無法解決的NP完備問題。生物分子計(jì)算機(jī)的研制是基于生物分子的信息處理技術(shù)，即生物材料的信息處理功能與生物分子的計(jì)算技術(shù)。 能以疊加方式存貯信息的量子計(jì)算可生成一些真正的隨機(jī)數(shù)，這是傳統(tǒng)計(jì)算機(jī)無能為力的。數(shù)學(xué)上已證明量子計(jì)算可大大加快因式分解的速度。這一證據(jù)也吸引人們將注意力集中在根據(jù)量子力學(xué)原理制造量子計(jì)算機(jī)上。 計(jì)算能力超越圖靈機(jī)、突破現(xiàn)有的體系結(jié)構(gòu)是計(jì)算業(yè)界的夢(mèng)想，不斷有報(bào)道在DNA計(jì)算模型上找到了某NP問題的多項(xiàng)式算法,這應(yīng)該意味著基于DNA計(jì)算模型的P類和NP類的劃分會(huì)和經(jīng)典模型有所不同。但是我們?nèi)匀幌Ｍ孔佑?jì)算能夠突破圖靈模式，給計(jì)算機(jī)科學(xué)帶來一個(gè)嶄新的世界。 哈密頓路徑問題 天文學(xué)家哈密頓(William Rowan Hamilton) 提出，在圖中找出一條包含所有結(jié)點(diǎn)的閉路，并且，出來起點(diǎn)和重點(diǎn)重合外，這條閉路所含結(jié)點(diǎn)是互不相同的，可以在多項(xiàng)式時(shí)間類判斷一個(gè)回路是否是哈密頓回路，但目前沒有算法直接解出哈密頓回路。 量子計(jì)算 量子計(jì)算(quantum computation)是對(duì)于一