1、從中國象棋(zhn u xin q)到NP完全問題【摘要(zhiyo)】 數學發展到21世紀，便和計算機的發展有了不解之緣。文章(wnzhng)從古老的象棋談起，圍繞計算機的的靈魂算法，也是數學最古老的本質論題，談到了數學機械化的可能性。通過對可計算理論和復雜性理論的闡述，引出“千禧年數學難題”中最重要的問題之一NP完全問題的基本理論和研究思想，在加深對NP完全性的理解之上，探討我們所生活的這個世界的本質所在，我們所研究的數學問題的本質所在以及它的終極結論。全文涉及到很多基本概念，主要內容是圍繞算法談論NP完全問題的來龍去脈，從思想上深入理解這一千年難題的根本所指。【關鍵字】 算法 機械證明

2、數學千年難題 計算復雜性 NP完全性 終極理論0. 引言這個世界的本質是什么？這是一個無人能回答的問題，也是一個值得人們永無止盡地去探求的問題。也許借助于“數學”這個人類至今所發明的最強有力的工具，我們會離答案更近一點。從萬物的起源談起，人類總不忘嘗試著去復原那遠古混沌的圖景，也渴望著發現終極理論來詮釋我們所在的宇宙。數學先于人類誕生，毋庸置疑！數學就是那萬物得以有序運行的機制所在，數學就是我們所渴求的終極理論的美妙琴弦！霍金借助于數學工具，寫出時間簡史，增進了我們認識宇宙的深度；菜場上的老大娘默默念叨著菜價，為生計精打細算；華爾街的金融師做著大量的分析和計算，預測出全球金融市場的風起云涌；活

3、躍在21世紀IT舞臺的精英們也在嘗試著把人類的實際需求轉化成一個個的程序，交給計算機去處理由此可見，數學的深入發展與人類的命運息息相關，不管是對個人還是群體。縱觀數學輝煌的發展史，在各類簡單的或是復雜的數學問題中，有沒有共通的東西呢？有！那就是算法！你會驚訝地發現，算法似乎就是數學的本質！任何在數學上已解決了的問題都可以交給算法去處理，任何運行的機制和運動的物體都可以用算法來描述！于是我們就有了這樣一個疑問：是否任何問題的解決都可以歸結為尋求到相應的算法？然而，情況并不樂觀，仍然存在著大量的不可計算的問題，也就是不能用算法來描述的問題讓人們困惑不已。事實上，我們現在所掌握的數學并不是完美的。就

4、像我們建立的現代科學體系，數學也只是對客觀世界的近似刻畫，是人類為獲得外界信息所發明的一個有力工具。類似于語言，數學使得先輩們的生活經驗得以記錄下來，數學符號使得人們精確思維有了載體。數學的不完美性和持續發展性也能夠從數學史上的三大悖論窺得，而每一個難題的解決則是人類思維升華、大腦進化的必然過程！數學需要深刻的思考，而正是這深入的思考促進了社會的發展。當不可思議的悖論發生的時候，那必然是我們的工具出了漏洞，在苦苦思索之后，我們的蒙昧與無知得到洗滌，我們對世界的認識也更加深入了。本文較系統地闡述了算法的一個高級(goj)話題NP難問題(wnt)的其來龍去脈。文章從古老的中國象棋談起，深入認識算法

5、的本質，并由此延伸到數學(shxu)的機械化。在對當今世界數學七大難題核心思想的了解下，進一步探析了計算復雜性的理論。文章最后圍繞NP難問題，嘗試著使其在思維上明朗化，以擺脫框框條條的束縛，站在哲學的高度來審視數學的本質所在，從而提高我們認識世界的廣度和深度。1. 美妙的算法1997年5月，深藍第二次次挑戰國際象棋世界冠軍卡斯巴羅夫，比賽在5月11日結束，最終深藍電腦以3.5：2.5擊敗卡斯巴羅夫，成為首個在標準比賽時限內擊敗國際象棋世界冠軍的電腦系統。深藍戰勝人腦的根本所在在于它使用了更加優良的算法，而國際象棋大師的腦海中也儲存了大量的棋譜和固有的邏輯推理。中國古代象棋也是一種基于推理的益智

6、游戲，它是對古代戰爭的抽象模擬，對提高戰將們的邏輯推理和思維的嚴密性很有幫助。弈棋高手大都熟悉很多棋譜（如下圖所示），而那一張張棋譜實際上就是某一算法確定的一步，誰的算法更優，誰就能贏得棋局。 圖1-0 中國象棋 圖1-1 棋譜1.1 算法的定義那么到底什么是算法呢？算法可以理解為有基本運算及規定的運算順序所構成的完整的解題步驟。或者看成按照要求設計好的有限的確切的計算序列，并且這樣的步驟和序列可以解決一類問題。定義1.1 算法是求解問題類的、機械的、統一的方法，它由有限多個步驟組成，對于問題類中的每個給定的具體問題，機械地執行這些步驟就可以得到問題的解答。正是由于算法的這種特性，才使得計算不

7、僅可以由人，而且可以由計算機來完成。這也是深藍得以戰勝人腦的依據所在。用計算機解決問題的過程可以分成三個階段：分析問題、設計算法和實現算法。1.2 算法的歷史中國古代的籌算口訣與珠算口訣及其執行規則就是算法的雛形，這里，所解決的問題類是算術運算。古希臘數學家歐幾里得在公元前3世紀就提出了一個算法，來尋求兩個正整數的最大公約數，這就是有名的歐幾里得算法，亦稱輾轉相除法。中國早已有“算術”、“算法”等詞匯，但是它們的含義是指當時的全部數學知識和計算技能，與現代算法的含義不盡相同。英文algorithm(算法)一詞也經歷了一個演變過程，最初的拼法為algorism或algoritmi，原意為用阿拉伯

8、數字進行計算的過程。這個詞源于公元 9世紀波斯數字家阿爾花拉子米的名字的最后一部分。在古代，計算通常是指數值計算。現代計算已經遠遠地突破了數值計算的范圍，包括大量的非數值計算，例如(lr)檢索、表格處理、判斷、決策、形式邏輯演繹等。歐幾里得算法被人們認為是史上第一個算法。第一次編寫(binxi)程序是Ada Byron于1842年為巴貝奇分析機編寫求解伯努利方程的程序，因此Ada Byron被大多數人認為是世界上第一位程序員。因為查爾斯巴貝奇(Charles Babbage)未能完成他的巴貝奇分析機，這個(zh ge)算法未能在巴貝奇分析機上執行。因為“well-defined procedu

9、re”缺少數學上精確的定義，19世紀和20世紀早期的數學家、邏輯學家在定義算法上出現了困難。20世紀的英國數學家圖靈提出了著名的圖靈論題，并提出一種假想的計算機的抽象模型，這個模型被稱為圖靈機。圖靈機的出現解決了算法定義的難題，圖靈的思想對算法的發展起到了重要作用的。在20世紀以前，人們普遍地認為，所有的問題類都是有算法的。20世紀初，數字家們發現有的問題類是不存在算法的，遂開始進行可行性研究。在這一研究中，現代算法的概念逐步明確起來。30年代，數字家們提出了遞歸函數、圖靈機等計算模型，并提出了丘奇圖靈論題，這才有可能把算法概念形式化。按照丘奇-圖靈論題，任意一個算法都可以用一個圖靈機來實現，

10、反之，任意一個圖靈機都表示一個算法。按照上述理解，算法是由有限多個步驟組成的，它有下述兩個基本特征：每個步驟都明確地規定要執行何種操作；每個步驟都可以被人或機器在有限的時間內完成。人們對于算法還有另一種不同的理解，它要求算法除了上述兩個基本特征外，還要具有第三個基本特征：雖然有些步驟可能被反復執行多次，但是在執行有限多次之后，就一定能夠得到問題的解答。也就是說，一個處處停機（即對任意輸入都停機）的圖靈機才表示一個算法，而每個算法都可以被一個處處停機的圖靈機來實現1.3 算法分類算法可大致分為基本算法、數據結構的算法、數論與代數算法、計算幾何的算法、圖論的算法、動態規劃以及數值分析、加密算法、排

11、序算法、檢索算法、隨機化算法、并行算法等。算法還可以宏泛的分為三類：有限的，確定性算法 這類算法在有限的一段時間內終止。他們可能要花很長時間來執行指定的任務，但仍將在一定的時間內終止。這類算法得出的結果常取決于輸入值。有限的，非確定算法 這類算法在有限的時間內終止。然而，對于一個（或一些）給定的數值，算法的結果并不是唯一的或確定的。無限(wxin)的算法 是那些由于沒有定義終止定義條件(tiojin)，或定義的條件無法由輸入的數據滿足而不終止運行的算法。通常，無限算法的產生是由于未能確定的定義終止條件。1.4 算法(sun f)的特征一個算法應該具有以下五個方面的重要特征：輸入 一個算法有零個

12、或多個輸入，以刻畫運算對象的初始情況。例如，在歐幾里得算法中，有兩個輸入，即m和n。確定性 算法的每一個步驟必須要確切地定義。即算法中所有有待執行的動作必須嚴格而不含混地進行規定，不能有歧義性。例如，歐幾里得算法中，步驟1中明確規定”以m除以n，而不能有類似以m除n以或n除以m這類有兩種可能做法的規定。有窮性 一個算法在執行有窮步滯后必須結束。也就是說，一個算法，它所包含的計算步驟是有限的。例如，在歐幾里得算法中，m和n均為正整數，在步驟1之后，r必小于n，若r不等于0，下一次進行步驟1時，n的值已經減小，而正整數的遞降序列最后必然要終止。因此，無論給定m和n的原始值有多大，步驟1的執行都是有

13、窮次。輸出 算法有一個或多個的輸出，即與輸入有某個特定關系的量，簡單地說就是算法的最終結果。例如，在歐幾里得算法中只有一個輸出，即步驟2中的n。可行性 算法中有待執行的運算和操作必須是相當基本的，換言之，他們都是能夠精確地進行的，算法執行者甚至不需要掌握算法的含義即可根據該算法的每一步驟要求進行操作，并最終得出正確的結果。1.5 算法的基本方法下面簡單介紹算法的一些基本方法，而基于這些方法的分治策略、貪心策略、動態規劃策略、分支限界法、回溯法等則是五種通用的算法設計技術。遞推法 遞推法是利用問題本身所具有的一種遞推關系求問題解的一種方法。它把問題分成若干步，找出相鄰幾步的關系，從而達到目的。遞

14、歸法 遞歸指的是一個過程：函數不斷引用自身，直到引用的對象已知。窮舉搜索法 窮舉搜索法是對可能是解的眾多候選解按某種順序進行逐一枚舉和檢驗，并從中找出那些符合要求的候選解作為問題的解。貪婪法 貪婪法是一種不追求最優解，只希望得到較為滿意解的方法。貪婪法一般可以快速得到滿意的解，因為它省去了為找最優解要窮盡所有可能而必須耗費的大量時間。貪婪法常以當前情況為基礎作最優選擇，而不考慮各種可能的整體情況，所以貪婪法不要回溯。分治(fn zh)法 分治法是把一個復雜(fz)的問題分成兩個或更多的相同或相似的子問題，再把子問題分成更小的子問題直到最后子問題可以簡單(jindn)的直接求解，原問題的解即子問

15、題的解的合并。動態規劃法 動態規劃是一種在數學和計算機科學中使用的，用于求解包含重疊子問題的最優化問題的方法。其基本思想是，將原問題分解為相似的子問題，在求解的過程中通過子問題的解求出原問題的解。動態規劃的思想是多種算法的基礎，被廣泛應用于計算機科學和工程領域。 迭代法 迭代法是數值分析中通過從一個初始估計出發尋找一系列近似解來解決問題（一般是解方程或者方程組）的過程，為實現這一過程所使用的方法統稱為迭代法。分支界限法 與貪婪算法一樣，這種方法也是用來為組合優化問題設計求解算法的，所不同的是它在問題的整個可能解空間搜索，所設計出來的算法雖其時間復雜度比貪婪算法高，但它的優點是與窮舉法類似，都能

16、保證求出問題的最佳解，而且這種方法不是盲目的窮舉搜索，而是在搜索過程中通過限界，可以中途停止對某些不可能得到最優解的子空間進一步搜索（類似于人工智能中的剪枝），故它比窮舉法效率更高。1.6 典型算法舉例算法可以用自然語言描述。自然語言是人們日常所用的語言，如漢語、英語、德語等。使用這些語言不用專門訓練，所描述的算法也通俗易懂。算法也可以用流程圖描述。在數學課程里，我們學習了用程序框圖來描述算法。在程序框圖中流程圖是描述算法的常用工具，即由一些圖形符號來表示算法。算法還可以用偽代碼描述。偽代碼是用介于自然語言和計算機語言之間的文字和符號來描述算法的工具。它不用圖形符號，因此，書寫方便、格式緊湊，

17、易于理解，便于向計算機程序設計語言過度。公元前250年古希臘的數學家埃拉托塞尼提出一種篩法來求素數，下面我們用自然語言來描述該算法：Step1 要得到不大于某個自然數N的所有素數，只要在2N中將不大于N的素數的倍數全部劃去即可。Step2 將上面的內容等價轉換：“如果N是合數，則它有一個因子d滿足1dN”。Step3 再將Step2的內容等價轉換：“若自然數N不能被不大于N的任何素數整除，則N是一個素數”。Step4 這句話的漢字可以等價轉換成為用英文字母表達的公式： N = p1m1+a1 = p2m2+a 2= =pkmk+ak. (1) 其中(qzhng)p1，p2， ，pk表示順序(s

18、hnx)素數2，3，5， ，a0。即N不能是2m+0，3m+0，5m+0， ，pkm+0形。若NP（k+1）的平方，則N是一個(y )素數。Step5 可以把(1)等價轉換成為用同余式組表示： Na1(modp1)，Na2(modp2)， ，Nak(modpk). (2)例1.6.1 29不能夠被根號29以下的任何素數2，3，5整除，29=214+1=39+2=55+4。291(mod2)，292(mod3)，294(mod5)。29小于7的平方49，所以29是一個素數。由于(2)的模p1，p2，pk 兩兩互素，根據孫子定理(中國剩余定理）知，(2)在p1pk范圍內有唯一解。例1.6.2 k=

19、1時，N=2m+1，解得N=3，5，7。求得了（3，32）區間的全部素數。k=2時，N=2m1+1=3m2+1，解得N=7，13，19； N=2m1+1=3m2+2，解得N=5，11，17，23。求得了（5，52）區間的全部素數。k=3時，N=2m1+1=3m2+1=(5m3+1/5m3+2/5m3+3/5m3+4)，解得N=13，19，31，37，43。N=2m1+1=3m2+2=(5m3+1/5m3+2/5m3+3/5m3+4)，解得N=11，17，23，29，41，47。求得了（7，72）區間的全部素數。仿此下去，可以求得任意大的數以內的全部素數。2. 數學機械化數學問題的機械化，就是要

20、求在運算或證明過程中，每前進一步之后，都有一個確定的、必須選擇的下一步，這樣沿著一條有規律的、刻板的道路，一直達到結論。即所謂的機械化就是刻板化和規格化。這一起源于中國古代傳統數學，由于計算機的出現而呈現旺盛生命力的數學機械化思想在數學研究上已經發揮出它的巨大威力，并且對當今數學及數學教學產生了具大的影響。計算機科學被認為是算法的科學。以算法為核心的機械化思想，既傳統又前瞻，將為信息時代數學科學的創新發揮重大作用。“計算機證明數學問題”是由吳文俊提出的，華人美籍數學家王浩也是最初的研究人員之一。它是極為神奇的超級工程數學，有可能引發工程技術的革命和某些基礎數學的革命。數學機械化研究，是在初等幾

21、何定理的 HYPERLINK /view/380555.htm t _blank 機器證明研究方面取得突破的。公理化體系的幾何定理證明非常靈活。以中學課程中的幾何為例，個定理的證明，往往要經過冥思苦想，奇巧構思，無章可循地填加輔助線，迂回曲折地給出證明。如何利用計算機進行自動推理，特別是進行幾何定理的自動證明，是學術界長期研究的課題。所謂定理的機械化證明，就是對一類定理（這類定理可能成千上萬）提供一種統一的方法，使得該類定理中每個定理，都可依此方法給出證明。在證明過程中，每前進一步，都有章可循地確定下一步該做什么和如何做。從“一理一證”到“類一證”，是數學的認識和實踐的飛躍。吳先生創立了初等幾

22、何（泛指不具有微分運算的幾何，如歐氏幾何、非歐幾何、仿射幾何、投影幾何、代數幾何等等）定理證明的機械化方法，國際上稱“ HYPERLINK /view/658127.htm t _blank 吳方法”，首次實現了高效的幾何定理的機器證明。“吳方法”也可用于幾何定理的自動發現和未知關系的自動推導。吳文俊先生的開創性成果，打破了國際自動推理界在幾何定理自動證明研究中長期徘徊不前的局面，也使我國在這一領域處于領先地位。數學(shxu)是研究數量關系和形體性質的科學。“數”與“形”在現實世界中無處不在，因此，數學科學是自然科學的基礎，也是高新技術的基礎，甚至是工程建設的基礎，這已是人們的共識。數學科學

23、的好處(ho chu)是，可以化難為易，把奧妙變為常識，為各類問題的解決提供框架。吳文俊先生(xin sheng)強調：“數學機械化方法的應用，是數學機械化研究的生命線”。他本人的研究工作己涉及許多應用領域，如線性控制系統、機構綜合設計、平面星體運行的中心構形、化學反應方程的平衡、代數曲面的光滑拼接、從開普勒定律自動推出牛頓定律、全局優化求解等等。在他的指導和帶動下，數學機械化方法己在一些交叉研究領域獲得初步應用，如理論物理、計算機科學、信息科學、自動推理、工程幾何、機械機構學等等。數學機械化研究不斷開拓更多的應用方面。吳文俊先生說過，從事數學研究，要有良好的思維方式，在思想觀念上要有所突破。

24、許多事例表明，些數學分支正是由于踏上了機械化的道路而獲得了蓬勃的發展，使之成為重要的研究方向，甚至成為數學的主流。這是因為，抽象的數學概念和結論，往往是難于掌握和運用的。當把抽象的概念變成具體可算的（算法經常用公式表達），既有定性的結論又有定量的計算，數學理論才臻于完善，易于接受和適宜應用。運用機械化思想考察數學，將會發現數學的不同側面，建立新的模式，活躍和啟迪數學家的思維，從而產生大量的原始創新。證定理和解方程，大體上涵蓋了數學活動的主要內容。在機器證定理和機器解方程兩個方面，吳文俊先生在理論和方法上都做出了原創性的貢獻。機器定理證明 機器定理證明就是把人證明數學定理和日常生活中的演繹推理變

25、成一系列能在計算機上自動實現的符號演算的過程和技術，又稱自動定理證明和自動演繹。機器定理證明是人工智能的重要研究領域，它的成果可應用于問題求解、自然語言理解、程序驗證和自動程序設計等方面。數學定理證明的過程盡管每一步都很嚴格有據，但決定采取什么樣的證明步驟，卻依賴于經驗、直覺、想象力和洞察力，需要人的智能。因此，數學定理的機器證明和其他類型的問題求解，就成為人工智能研究的起點。早在17世紀中葉，萊布尼茲就提出過用機器實現定理證明的思想。19世紀后期G.弗雷格的“思想語言”的形式系統，即后來的謂詞演算，奠定了符號邏輯的基礎，為自動演繹推理提供了必要的理論工具。20世紀50年代，由于數理邏輯的發展

26、，特別是電子計算機的產生和應用，機器定理證明才變為現實。A.紐厄爾和H.A.西蒙首先用探試法實現了用以證明命題邏輯中重言式的邏輯理論家系統。L.T.后來開始探討通用的機器定理證明的方法，歸結原理是其中突出的例子。歸結原理和非歸結定理證明 一階謂詞邏輯的恒真性問題是不可解的，即不存在能判定一階邏輯中任意合式公式是不是永真式的算法，但是這個問題又是部分可解的。如果A是永真式，那么必有算法可以證明。許多一階邏輯的證明算法都以J.厄爾布朗定理為基礎，其中以1965年J.A.魯賓遜提出的、對于一階邏輯是完備的證明算法即歸結原理最為著名。歸結原理的提出，把機器定理證明的研究推向高潮。但歸結原理不依賴于領域

27、知識，不使用依賴問題領域的探試法，證明過程冗長，不能在合理的時間和計算機存儲容量內證明較為復雜的數學定理，因此人們又提出非歸結定理證明方法，后來又對以探試法為基礎的問題求解技術發生興趣。與此同時還出現了因否定歸結原理進而否定所有自動演繹方法的傾向。但是人工智能所要解決的問題，其信息往往是不完全的，而且即使信息完全，要對有限的但為數眾多的情形一一列舉，實際上也不可行，因而只有用演繹推理的方法。邏輯程序設計和日本以PROLOG為原型開發第五代計算機系統的核語言，進一步恢復了歸結原理和自動演繹技術的地位。人工智能的歷史表明，以認知心理學為基礎的探試法和以邏輯為基礎的自動演繹相輔相成，不可偏廢。自動演

28、繹與探試法等技術相結合而不用歸結原理的定理證明技術，主要用于數學定理的機器證明。幾何定理的機器(j q)證明 在數學定理機器證明中，有一類問題已有判定算法，如1951年W。斯米列夫給出的阿貝爾群判定算法，1951年A.塔斯基給出的初等幾何和代數的判定算法，1960年王浩提出的命題邏輯判定算法和1976年以來(yli)吳文俊提出的初等幾何和微分幾何定理機器證明的理論和方法。非標準邏輯(lu j)中的自動演繹 以經典的一階邏輯為基礎的自動演繹技術比較成熟。為了適應人工智能中復雜的推理形式，需要研究高階邏輯和非標準邏輯中的自動演繹技術并從實用角度將這類邏輯表示形式轉換成等價的經典一階邏輯的表示形式。

29、邏輯程序設計 將一階謂詞演算的子集直接作為程序設計語言的技術和方法。PROLOG語言是初步實現邏輯程序設計基本思想的第一個語言，R.科瓦爾斯基則曾對HORN子句作了過程性解釋，系統地闡明了邏輯程序設計的基本理論。3. 千年大獎問題20世紀是數學大發展的一個世紀。數學的許多重大難題得到完滿解決，如費馬大定理的證明，有限單群分類工作的完成等，從而使數學的基本理論得到空前發展。計算機的出現是20世紀數學發展的重大成就，同時極大推動了數學理論的深化和數學在社會和生產力第一線的直接應用。回首20世紀數學的發展，數學家們深切感謝20世紀最偉大的數學大師大衛希爾伯特。希爾伯特在1900年8月8日于巴黎召開的

30、第二屆世界數學家大會上的著名演講中提出了23個數學難題。希爾伯特問題在過去百年中激發數學家的智慧，指引數學前進的方向，其對數學發展的影響和推動是巨大的，無法估量的。效法希爾伯特，許多當代世界著名的數學家在過去幾年中整理和提出新的數學難題，希冀為新世紀數學的發展指明方向。這些數學家知名度是高的，但他們的這項行動并沒有引起世界數學界的共同關注。2000年初美國克雷數學研究所的科學顧問委員會選定了七個“千年大獎問題”，克雷數學研究所的董事會決定建立七百萬美元的大獎基金，每個“千年大獎問題”的解決都可獲得百萬美元的獎勵。克雷數學研究所“千年大獎問題”的選定，其目的不是為了形成新世紀數學發展的新方向，而

31、是集中在對數學發展具有中心意義、數學家們夢寐以求而期待解決的重大難題。2000年5月24日，千年數學會議在著名的法蘭西學院舉行。會上，98年費爾茲獎獲得者伽沃斯以“數學的重要性”為題作了演講，其后，塔特和阿啼亞公布和介紹了這七個“千年大獎問題”。克雷數學研究所還邀請有關研究領域的專家對每一個問題進行了較詳細的闡述。克雷數學研究所對“千年大獎問題”的解決與獲獎作了嚴格規定。每一個“千年大獎問題”獲得解決并不能立即得獎。任何解決答案必須在具有世界聲譽的數學雜志上發表兩年后且得到數學界的認可，才有可能由克雷數學研究所的科學顧問委員會審查決定是否值得獲得百萬美元大獎。“千年(qin nin)大獎問題”

32、公布以來，在世界數學界產生(chnshng)了強烈反響。這些問題都是關于數學基本理論的，但這些問題的解決將對數學理論的發展和應用的深化產生巨大推動。認識和研究“千年(qin nin)大獎問題”已成為世界數學界的熱點。不少國家的數學家正在組織聯合攻關。可以預期，“千年大獎問題”將會改變新世紀數學發展的歷史進程。這七個“千年大獎問題”分別是：NP完全問題、霍奇猜想、龐加萊猜想、黎曼假設、楊米爾斯理論、納衛爾斯托可方程、BSD猜想。難題一 P(Polynomial算法)問題對NP(Non-deterministic Polynomial算法)問題在一個周六的晚上，你參加了一個盛大的晚會。由于感到局促

33、不安，你想知道這一大廳中是否有你已經認識的人。你的主人向你提議說，你一定認識那位正在甜點盤附近角落的女士羅絲。不費一秒鐘，你就能向那里掃視，并且發現你的主人是正確的。然而，如果沒有這樣的暗示，你就必須環顧整個大廳，一個個地審視每一個人，看是否有你認識的人。生成問題的一個解通常比驗證一個給定的解時間花費要多得多。這是這種一般現象的一個例子。與此類似的是，如果某人告訴你，數13，717，421可以寫成兩個較小的數的乘積，你可能不知道是否應該相信他，但是如果他告訴你它可以因子分解為3607乘上3803，那么你就可以用一個袖珍計算器容易驗證這是對的。不管我們編寫程序是否靈巧，判定一個答案是可以很快利用

34、內部知識來驗證，還是沒有這樣的提示而需要花費大量時間來求解，被看作邏輯和計算機科學中最突出的問題之一。NP完全問題是不確定性圖靈機在P時間內能解決的問題。整個計算機科學的大廈就建立在圖靈機可計算理論和計算復雜性理論的基礎上，一旦證明P=NP，將是計算機科學的一場決定性的突破，在軟件工程實踐中，將革命性的提高效率。從工業，農業，軍事，醫療到生活，軟件在它的各個應用域，都將是一個飛躍。P=NP嗎? 這個問題是著名計算機科學家(1982年圖靈獎得主)斯蒂文考克（StephenCook）于1971年發現并提出的。難題二 霍奇(Hodge)猜想二十世紀的數學家們發現了研究復雜對象的形狀的強有力的辦法。基

35、本想法是問在怎樣的程度上，我們可以把給定對象的形狀通過把維數不斷增加的簡單幾何營造塊粘合在一起來形成。這種技巧是變得如此有用，使得它可以用許多不同的方式來推廣；最終導致一些強有力的工具的發明，使數學家在對他們研究中所遇到的形形色色的對象進行分類時取得巨大的進展。不幸的是，在這一推廣中，程序的幾何出發點變得模糊起來。在某種意義下，必須加上某些沒有任何幾何解釋的部件。霍奇猜想斷言，對于所謂射影代數簇這種特別完美的空間類型來說，稱作霍奇閉鏈的部件實際上是稱作代數閉鏈的幾何部件的(有理線性)組合。難題(nnt)三 龐加萊(Poincare)猜想(cixing) 如果我們伸縮圍繞一個蘋果表面(biomi

36、n)的橡皮帶，那么我們可以既不扯斷它，也不讓它離開表面，使它慢慢移動收縮為一個點。另一方面，如果我們想象同樣的橡皮帶以適當的方向被伸縮在一個輪胎面上，那么不扯斷橡皮帶或者輪胎面，是沒有辦法把它收縮到一點的。我們說，蘋果表面是“單連通的”，而輪胎面不是。大約在一百年以前，龐加萊已經知道，二維球面本質上可由單連通性來刻畫，他提出三維球面(四維空間中與原點有單位距離的點的全體)的對應問題。這個問題立即變得無比困難，從那時起，數學家們就在為此奮斗。龐加萊猜想，已被我國中山大學朱熹平教授和旅美數學家、清華大學兼職教授曹懷東破解了。難題四 黎曼(Riemann)假設 有些數具有不能表示為兩個更小的數的乘積

37、的特殊性質，例如，2，3，5，7，等等。這樣的數稱為素數；它們在純數學及其應用中都起著重要作用。在所有自然數中，這種素數的分布并不遵循任何有規則的模式；然而，德國數學家黎曼(1826-1866)觀察到，素數的頻率緊密相關于一個精心構造的所謂黎曼函數z(s)的性態。著名的黎曼假設斷言，方程z(s)=0的所有有意義的解都在一條直線上。這點已經對于開始的1,500,000,000個解驗證過。證明它對于每一個有意義的解都成立將為圍繞素數分布的許多奧秘帶來光明。 難題五 楊米爾斯(Yang-Mills)存在性和質量缺口 量子物理的定律是以經典力學的牛頓定律對宏觀世界的方式對基本粒子世界成立的。大約半個世

38、紀以前，楊振寧和米爾斯發現，量子物理揭示了在基本粒子物理與幾何對象的數學之間的令人注目的關系。基于楊米爾斯方程的預言已經在如下的全世界范圍內的實驗室中所履行的高能實驗中得到證實：布羅克哈文、斯坦福、歐洲粒子物理研究所和駐波。盡管如此，他們的既描述重粒子、又在數學上嚴格的方程沒有已知的解。特別是，被大多數物理學家所確認、并且在他們的對于“夸克” 的不可見性的解釋中應用的“質量缺口”假設，從來沒有得到一個數學上令人滿意的證實。在這一問題上的進展需要在物理上和數學上兩方面引進根本上的新觀念。難題六 納維葉斯托克斯(Navier-Stokes)方程的存在性與光滑性 起伏的波浪跟隨著我們的正在湖中蜿蜒穿

39、梭的小船，湍急的氣流跟隨著我們的現代噴氣式飛機的飛行。數學家和物理學家深信，無論是微風還是湍流，都可以通過理解納維葉斯托克斯方程的解，來對它們進行解釋和預言。雖然這些方程是19世紀寫下的，我們對它們的理解仍然極少。挑戰在于對數學理論做出實質性的進展，使我們能解開隱藏在納維葉斯托克斯方程中的奧秘。難題七 貝赫(Birch)和斯維納通戴爾(Swinnerton-Dyer)猜想 數學家總是被諸如x2+y2=z2那樣的代數方程的所有整數解的刻畫問題著迷。歐幾里德曾經對這一方程給出完全的解答，但是對于更為復雜的方程，這就變得極為困難。事實上，正如馬蒂雅謝維奇(Yu.V.Matiyasevich)指出，希

40、爾伯特第十問題是不可解的，即，不存在一般的方法來確定這樣的方法是否有一個整數解。當解是一個阿貝爾簇的點時，貝赫和斯維訥通戴爾猜想認為，有理點的群的大小與一個有關的函數z(s)在點s=1附近的性態。特別是，這個有趣的猜想認為，如果z(1)等于0，那么存在無限多個有理點(解)，相反，如果z(1)不等于0，那么只存在有限多個這樣的點。由上看出，NP完全(wnqun)問題排在七個“千僖年數學(shxu)難題”百萬美元大獎的首位，足見他的顯赫地位和無窮魅力。NP完全(wnqun)問題是NP類中“最難”的問題，也就是說它們是最可能不屬于P類的。這是因為任何NP中的問題可以在多項式時間內變換成為任何特定NP

41、完全問題的一個特例。多流水線調度實際上是一個NP完全問題數學上著名的NP問題，完整的叫法是NP完全問題。在第6節中我們會對NP完全問題給出較詳細的闡述。4. 可計算性可計算性理論是計算機科學的理論基礎之一。早在30年代，圖靈對存在通用圖靈機的邏輯證明表明，制造出可通過編程解決任何計算的通用計算機是可能的，這影響了40年代出現的存儲程序計算機（即諾伊曼型計算機）的設計思想。可計算性理論確定了哪些問題可能用計算機解決，哪些問題不可能用計算機解決。研究計算的一般性質的數學理論，也稱算法理論或能行性理論。它通過建立計算的數學模型（例如抽象計算機），精確區分哪些是可計算的，哪些是不可計算的。計算的過程就

42、是執行算法的過程。可計算性理論的重要課題之一，是將算法這一直觀概念精確化。算法概念精確化的途徑很多，其中之一是通過定義抽象計算機，把算法看作抽象計算機的程序。通常把那些存在算法計算其值的函數叫可計算函數。因此，可計算函數的精確定義為：能夠在抽象計算機上編出程序計算其值的函數。這樣就可以討論哪些函數是可計算的，哪些函數是不可計算的。4.1 可計算性的產生可計算性理論起源于對數學基礎問題的研究。20世紀30年代，為了討論是否對于每個問題都有解決它的算法，數理邏輯學家提出了幾種不同的算法定義。K.哥德爾和S.C.克林尼提出了遞歸函數的概念，A.丘奇提出轉換演算， A.M.圖靈和E.波斯特各自獨立地提

43、出了抽象計算機的概念（后人把圖靈提出的抽象計算機稱為圖靈機），并且證明了這些數學模型的計算能力是一樣的，即它們是等價的。著名的丘奇-圖靈論題也是丘奇和圖靈在這一時期各自獨立提出的。后來，人們又提出許多等價的數學模型，如A.馬爾可夫于40年代提出的正規算法（后人稱之為馬爾可夫算法），60年代前期提出的隨機存取機器模型（簡稱 RAM）等。50年代末和60年代初，胡世華和J.麥克阿瑟等人各自獨立地提出了定義在字符串上的遞歸函數。4.2 可計算性的內容 若m和n是兩個正整數，且mn，求m和n的最大公因子的歐幾里得算法可表示為：E1求余數以n 除m 得余數r。E2余數為0嗎?若r0，計算結束，n即為答案

44、；否則轉到步驟E3。E3互換把m的值變為n，n的值變為r，重復上述步驟。依照這三條規則指示的步驟，可計算出任何兩個正整數的最大公因子。可以把計算過程(guchng)看成執行這些步驟的序列。我們發現，計算過程是有窮的，而且計算的每一步都是能夠機械實現的（機械性）。為了精確刻畫算法的特征，人們建立了各種各樣的數學模型。4.3 重要(zhngyo)概念4.3.1 圖靈機一種在理論計算機科學中廣泛(gungfn)采用的抽象計算機，它是圖靈在1936年提出的，用于精確描述算法的特征。可用一個圖靈機來計算其值的函數是可計算函數，找不到圖靈機來計算其值的函數是不可計算函數。可以證明，存在一個圖靈機U，它可以

45、模擬任何其他的圖靈機。這樣的圖靈機U稱為通用圖靈機。通用圖靈機正是后來出現的存儲指令的通用數字計算機的理論原型。4.3.2 轉換演算 一種定義函數的形式演算系統，是A.丘奇于1935年為精確定義可計算性而提出的。他引進記號以明確區分函數和函數值，并把函數值的計算歸結為按一定規則進行一系列轉換，最后得到函數值。按照轉換演算能夠得到函數值的那些函數稱為可定義函數。 4.3.3 丘奇-圖靈論題 可計算性理論的基本論題，也稱圖靈論題，它規定了直觀可計算函數的精確含義。丘奇論題說：可定義函數類與直觀可計算函數類相同。圖靈論題說：圖靈機可計算函數類與直觀可計算函數類相同。圖靈證明了圖靈機可計算函數類與可定

46、義函數類相同。這表明圖靈論題和丘奇論題講的是一回事，因此把它們統稱為丘奇圖靈論題。直觀可計算函數不是一個精確的數學概念，因此丘奇-圖靈論題是不能加以證明的。30年代以來，人們提出了許多不同的計算模型來精確刻劃可計算性，并且證明了這些模型都與圖靈機等價。這表明圖靈機和其他等價的模型確實合理地定義了可計算性，因此丘奇圖靈論題得到了計算機科學界和數學界的公認。4.3.4 遞歸函數 原始遞歸函數 自變量值和函數值都是自然數的函數，稱為數論函數。原始遞歸函數是數論函數的一部分。首先規定少量顯然直觀可計算的函數為原始遞歸函數，它們是：函數值恒等于0的零函數C0，函數值等于自變量值加1的后繼函數S，函數值等

47、于第i個自變量值的n元投影函數P。然后規定，原始遞歸函數的合成仍是原始遞歸函數，可以由已知原始遞歸函數簡單遞歸地計算出函數值的函數仍是原始遞歸函數。例如，和函數f(x，y)=x+y可由原始遞歸函數P(1)1和S遞歸地計算出函數值 f(x，0)=P(1)1(x)f(x，S(y)=S(f(x，y)比如，f(4,2)可這樣計算，首先算出f(4,0)=P(1)1(4)=4，然后計算f(4,1)=S(f(4,0)=S(4)=5f(4,2)=S(f(4,1)=S(5)=6因此，和函數是原始遞歸函數。顯然，一切原始遞歸函數都是直觀可計算(j sun)的。許多常用的處處有定義的函數都是原始遞歸函數，但并非一切

48、直觀可計算的、處處有定義的函數都是原始遞歸函數。部分(b fen)遞歸函數 為了包括所有的直觀可計算函數，需要把原始(yunsh)遞歸函數類擴充為部分遞歸函數類。設g(x1，xn，z)是原始遞歸函數，如果存在自然數z使g(x1，xn，z)=0，就取f(x1，xn)的值為滿足g(x1，xn，z)=0的最小的自然數z；如果不存在使g(x1，xn，z)=0的自然數z，就稱f(x1，xn)無定義。把如上定義的函數f加到原始遞歸函數類中，就得到部分遞歸函數類。因為不能保證如上定義的f在一切點都有定義，故稱其為部分函數。處處有定義的部分遞歸函數稱為遞歸函數。部分遞歸函數類與圖靈機可計算函數類相同。對于每個

49、n元部分遞歸函數f，可以編一個計算機程序P，以自然數x1，xn作為輸入，若f(x1，xn)有定義，則P函數值執行終止并輸出的f(x1，xn)，否則P不終止。遞歸集 遞歸集最初是對于元素都是自然數的集合定義的，它們是有算法確定每個自然數是否為其元素的集合。可以將遞歸集的概念推廣到其他集合。所討論的對象的全體稱為域，如果有算法確定域中任意元素是否屬于A，則稱A為遞歸集。對于每個遞歸集，可以編一個計算機程序，以域中任意元素作為輸入，計算執行該程序都可給出適當的輸出，表明該元素是否屬于這個遞歸集。有許多集合不是遞歸集。遞歸可枚舉集 如果對于集合A可以編一個程序P，輸入域中任意元素x，若xA，則P的執行

50、將終止并輸出“是”，否則P 的執行不終止，就稱A為遞歸可枚舉集。A為遞歸可枚舉集的充分必要條件是可以編一個程序枚舉A的元素，即打印A的元素，使得對于 A中任意元素，只要時間足夠長總會在打印紙上出現。遞歸集都是遞歸可枚舉集，但有些遞歸可枚舉集不是遞歸集。有許多集合不是遞歸可枚舉集。4.3.5 可判定性和半可判定性 判定問題是無窮多個同類個別問題的總稱。例如，2是不是素數？6是不是素數？這些都是個別問題，把這類個別問題概括起來，就得到一個判定問題：任意給定的正整數是不是素數？這里的正整數集合稱為該判定問題的域，給定域中的一個元素，判定問題就對應一個個別問題。對于一個判定問題，如果能夠編出一個程序，

51、以域中任意元素作為輸入，執行該程序就能給出相應的個別問題的答案，就稱該判定問題為可判定的。例如，“任意正整數是不是素數”這個問題就是可判定的。對于集合A，域中任意元素是否屬于它的問題稱為集合 A對應的判定問題。集合是遞歸集的充分必要條件為對應的判定問題是可判定的。因此，全體素數的集合是遞歸集。對于一個判定問題，如果能夠編出一個程序P，以域中任意元素作為輸入，當相應的個別問題的解答是肯定的時候，P 的執行將終止并輸出“是”，否則P 的執行不終止，就稱該判定問題為半可判定的。可判定的問題總是半可判定的。集合是遞歸可枚舉集的充分必要條件為對應的判定問題是半可判定的。圖靈在1936年證明，圖靈機的停機

52、問題是不可判定的，即不存在一個圖靈機能夠判定任意圖靈機對于任意輸入是否停機。圖靈機的停機問題是半可判定的。圖靈機的停機問題是很重要的，由它可以推出計算機科學、數學(shxu)、邏輯學中的許多問題是不可判定的。5. 計算(j sun)復雜性計算復雜性是現代理論計算機科學中最重要的分支之一，它研究各種問題類在計算時所需要耗費的時間(shjin)、空間等資源的多少，是可計算性理論的新發展。5.1 從可計算性到計算復雜性 什么樣的問題類是可計算的？這是數學、數理邏輯學和早期計算機科學所關心的一個重要問題。為了回答這個問題，可以給出一個計算的模型，然后規定，凡是這個模型能計算的問題類就稱作可計算的，否則

53、就稱為不可計算的。于是產生了各種計算的模型：圖靈機、遞歸函數、 演算、馬爾可夫算法和遞歸算法等。但是，會不會有一類問題，在一個模型中是可計算的，而在另一個模型中卻是不可計算的呢？如果這樣，一個問題類的可計算性就依賴于模型，而不是問題類本身的性質了。著名的丘奇圖靈論題回答了這個問題。這個論題說：“凡是合理的計算模型都是等價的，即一個模型能算的問題類別的模型也能算，一個模型不能算的別的模型也不能算。”這個論題不是一個嚴格的命題，無法給出一般的證明，但可以對一個個具體的模型去驗證它的正確性。然而，對于一個問題類，只知道它能否計算還很不夠，更有實際意義的是要知道計算起來要耗費多少時間，要用多大的空間來

54、存儲計算的中間結果等等。為了回答這些進一步的問題，就產生了計算復雜性理論。5.2 資源計算時間、存儲大小都稱為資源。一般來說，各種模型的主要資源有并行時間、空間和串行時間三種。嚴格地講，每一種資源的定義都依賴于特定的計算模型。對各種計算模型，資源的定義雖不一樣，但主要的可分為三類。例如，對于多帶的圖靈機，就有串行時間、空間、巡回等資源。串行時間（簡稱時間） 它是計算過程中的總運算量，即把計算分成一些原始的步驟，完成這些步驟所需要的總時間。空間 它是為了保存中間結果所需要的存儲器的大小。例如在計算時用一塊黑板來打草稿，每一單位面積假定可以寫一個符號，不用了還可以擦掉。在計算時所需黑板面積就是空間

55、。并行時間它是并行計算所需要的時間，亦即如果多人或多處理機協同計算，解決一個問題所需要的時間。5.3 問題的大小和復雜性的度量和可計算性一樣，復雜性總是對于一個特定的問題類來討論的，它包括無窮多個個別問題，有大有小。例如，對矩陣乘法這樣一個問題類，相對地說，100階矩陣相乘是個大問題，而二階矩陣相乘就是個小問題。可以把矩陣的階n作為衡量問題大小(dxio)的尺度。又如在圖論問題中，可以把圖的頂點數n作為衡量問題大小的尺度。一個個別問題在計算之前，總要用某種方式加以編碼，并可把這個編碼的長度 n作為衡量問題大小的尺度。當給定一個(y )算法以后，計算大小為n的問題所需要的時間、空間等就可以表示為

56、 n的函數。這個函數就可作為該算法的時間或空間復雜性的度量。嚴格地講，是這個特定的問題類在某一特定計算模型中某一特定算法的復雜性之度量。當要解決的問題越來越大時，時間、空間等資源耗費將以什么樣的速率增長，即當n趨向于無窮大時，這個函數的性狀如何，增長的階是什么，這就是計算復雜性理論所要研究的主要問題。5.3.1 巡回(xnhu)和周相在上面提到的模型中，有的是串行模型，有的則是并行模型。如前所述，并行模型的串行時間相當于計算過程中的總運算量。至于串行模型的并行時間，可以認為它是一個叫作巡回的量。簡而言之，巡回是計算過程中周相的總數。而周相則是計算過程中的一個階段，在此階段內寫入工作空間的信息不

57、會在同一階段中讀出。由此可見，串行模型的巡回相應于并行模型的并行時間。對于一個問題類而言，存在一個高速并行算法的充要條件是可以找到一個具有小的巡回數的串行算法。5.3.2 相似性原理如上所述，一個問題類的時間、空間等資源的復雜性是依賴于模型的：在有的模型中較高，在另一些模型中則較低。現在較為重要而有特色的計算模型有：多帶圖靈機器、多變址隨機存取機器、存儲修改機器、齊一線路、向量機器、硬件修改機器等等。這樣一來，復雜性的問題仍然沒有一個統一的客觀依據。相似性原理解答了這個問題。按此原理，一個問題類內在的并行時間、空間和串行時間的復雜性在所有理想的計算模型中都沒有本質的差異。用數學的說法，各種模型

58、可以互相模擬，而且模擬者需用的并行時間、空間和串行時間都分別不超過被模擬者所需的并行時間、空間和串行時間的一個多項式，三者同時成立。所以在只差一個多項式的范圍內，復雜性的確是一個不依賴于模型的客觀實在。這是丘奇圖靈論題在復雜性理論中的新發展。對于上面提到的計算模型，相似性原理已被證明是正確的。以多帶圖靈機和向量機器為例，可以證明下面的相似性定理：設n是輸入字符串的長度，它代表問題的大小。對于任何一個多帶圖靈機，設它的巡回為R(n)，空間為S(n)，串行時間為T(n)，則一定有一個向量機器來模擬它，使得存在一個多項式p，向量機器的并行時間R1(n)，空間S1(n)和串行時間T1(n)滿足 R1(

59、n)p(R(n)S1(n)p(S(n)T1(n)p(T(n)在以上結論中把多帶圖靈機和向量機器的位置(wi zhi)對調一下也成立。這說明在多項式相關聯意義下，這兩個模型沒有本質的區別。因此，巡回是串行模型的虛擬并行時間。5.3.3 代數(dish)復雜性 相似性原理所涉及的模型主要研究計算中按位運算的總量時間，按位計的中間結果存儲量空間和計算的深度(并行時間)等等，所以可稱為按位的復雜性。代數的復雜性理論則研究在一個代數系統中（例如實數域中）從給定變量出發去計算某些函數所需要的代數運算（例如加法、乘法）代數判斷（例如大于或等于）的次數(時間)，所需中間變元的個數(空間)，計算的深度(并行時間

60、)等等。在實際運算中，既不能給出一個無限長的實數，也不能在一個單位時間內完成兩個實數的乘法。真正的算術運算都是通過近似小數的按位運算得出來的。所以按位的復雜性具有更為基本的意義。通過下面的例子，可以得到關于(guny)代數復雜性的一些感性認識。通常兩個n階矩陣相乘要做n3次數乘法，V.斯特拉森找到了一個算法，只需做次數乘法。此后這個上界又被許多人不斷改進到，至1981年12月，又改進為：D.科普爾史密斯和S.維諾格拉特還證明：最好的算法不存在，也就是說這個上界可以永遠改進下去。5.3.4 對偶性原理 并行時間和空間之間還呈現出某種對稱的性質，這就是對偶性原理。例如可以證明，對于一個問題類而言，