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

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