可計算性與計算復雜性李占山1000個圖片的拼圖，如果沒有考慮把握技巧，那么對于每個圖片有正反面、左右和對錯3種組合8種狀態，這樣我們把所有圖片拼在一起需要考慮81000種狀態（步驟）情況拼圖，這是一個驚人的數字，用計算機求解在我們的有生之年是看不到結果的。難道這個問題就沒有結果了嗎？非也，我們人不是在玩這種游戲嗎？我只用了一兩天甚至更短的時間就成功了，哪有你老師說的那么復雜？那樣不是很郁悶嗎？我拼圖成功很是快樂，為什么？拼圖游戲從拼圖游戲到解現實生活中的實際問題的解決---同學，游戲不是這樣玩的！我們的課程可以使你從可郁悶性與郁悶復雜性到可快樂性與快樂復雜性的。怎么辦？分類分解問題唄！首先把圖片都翻到相同一面，最壞時要做1000次，如果圖片字母標號有20種，然后把它們根據字母標號分成20子類，每一子類再根據字母正反分為2個子子類，同樣拼圖時相鄰的圖片是交錯排列的，按照這樣的分類方法進行拼圖看看最壞時我們需要多少個步驟？玩游戲是一門學問呦！1000+1000+20250個狀態（步驟），這些狀態步驟完全在你的有限時間掌控之中，因此能夠在一兩天甚至更短時間內完成拼圖任務。嗷！原來是這樣的呀！看來學好這門課會使我們從可郁悶性與郁悶復雜性到可快樂性與快樂復雜性的！！！為了學好這門課程我們有必要介紹這門課程的本質與定位以及一些重要歷史人物，他們是？？？？？

計算學科（ComputingScience）即我們所熟悉的計算機科學與技術(ComputerScienceandTechnology)。計算學科是對描述和變換信息的算法過程，包括其理論、分析、設計、效率分析、實現和應用等進行的系統研究的一門學科。它涉及計算過程的分析如可計算性、算法，研究有關計算機的各種現象、揭示其規律與本質如計算機的設計和使用、可計算性硬件和軟件的實際實現問題。

計算學科的基本問題是能行與效率的問題,即它的核心問題是“能行”問題(Practicability)：1)什么是（實際）可計算的？什么是（實際）不可計算的？2)如何保證計算的自動性、有效性及正確性？

1985年春，ACM（美國計算機協會）和IEEE－CS（國際電子電氣工程師學會計算機分會）組成聯合攻關小組，開始了對“計算作為一門學科”的存在性證明。1989年1月，該小組提交了《計算作為一門學科》（Computingasadiscipline）的報告。第一次給出了計算學科一個透徹的定義，回答了計算學科中長期以來一直爭論的一些問題，完成了計算學科的“存在性”證明，還提出了未來計算科學教育必須解決的二個重大問題――整個學科核心課程詳細設計及整個學科綜述性導引課程的構建。1991年，在這報告的基礎上提交了關于計算學科教學計劃CC1991（ComputingCurricula1991）。2001年12月，提交了最終的CC2001報告。

《計算作為一門學科》報告及CC1991、CC2001一起解決了三個重要問題：第一個重大問題（計算作為一門學科的存在性證明）的解決。對學科本身的發展至關重要。如果在眾多分支領域都取得了重大成果并已得到廣泛應用的“計算”，連作為一門學科的地位都不清楚，那么它的發展勢必要受到很大的限制。

第二個重大問題（整個學科核心課程詳細設計）的解決，將為高校制定計算機教學計劃奠定基礎。確定一個公認的本科生應該掌握的核心內容，將避免教學計劃設計中的隨意性，從而為我們科學地制定教學計劃奠定基礎。

第三個重大問題（整個學科綜述性導引課程的構建）的解決，將使人們對整個學科的認知科學化、系統化和邏輯化。如果人們對計算學科的認知能建立在公理化的基礎之上，則該學科可被認為是嚴謹的科學、成熟的學科，從而有助于它的發展，并將由此而得到人們的尊重。

攻關小組的結論是：計算學科所研究的根本問題是能行問題（什么能被（有效地）自動進行）。計算學科的基本原理已納入理論、抽象和設計這3個具有科學技術方法意義的過程中。學科的各分支領域正是通過這3個過程來實現它們各自的目標。而這3個過程要解決的都是計算過程中的“能行性”和“有效性”問題。

與數學相比，電子技術的重要性對計算科學而言不如數學，因為數學提供了計算科學最重要的學科思想和方法論基礎，而電子技術只提供了電子計算機的實現技術，它僅僅只是對計算科學許多思想和方法的一種當前最現實、最有效的實現技術手段而已。當科學技術的手段提到發展時，完全有可能有某一項新技術歸結為有效地取代電子技術（如光技術、生物技術等等），但計算科學的數學基礎可能變化不大。

從事計算科學的人都知道，計算科學中不僅許多理論是用數學描述的，而且許多技術也是用數學描述的。大多數計算科學理論不僅僅是對研究對象變化規律的陳述，而且由于能行性這一本質的核心問題和特點的作用，理論描述中常通過方法折射出技術的思想和步驟，而從理論通過方法跨越到技術則完全取決于理論的深刻認識和理解。一個人如果看懂了以形式化方法描述的技術文獻，自然明白技術上應該怎樣去做。

至于計算機技術專業的學生為何要學習數學這個問題的答案，了解了上面所講的計算學科與數學的關系后就不言而喻了：計算機科學植根于數學，但又不同于數學，從而可計算理論的基礎知識就需要掌握，因為這能夠提高我們本身的邏輯推理能力、抽象思維能力和形式化思維能力，從而今后在學習任何一門計算機科學的專業主干課程時，都不會遇上任何思維理解上的困難。

當前計算機科學在發展過程中面對著如下兩個問題：

一是信息革命要求計算機科學要將計算機的應用擴大到包含所有的問題領域和深入到每個問題領域的深處而越來越細致越來越復雜；二是一旦讓計算機去解決問題，那么計算機應自動地在有限和有效的時間內得出解。前者指出計算機科學的任務就是要用計算機的硬件、外設和軟件構成一個系統，使得許多不同領域的問題都能在這樣的計算機系統中得到解決。為了完成這個任務，就必須用一種符號語言構成一個包括了不同領域的通用模型。

計算理論就是指出構成一個包括了不同領域的通用模型的思維方法，并且告訴我們怎樣用不同的語言（符號語言、圖形語言、邏輯語言等）從最簡單的對象（集合）出發表示通用模型。后者指出計算機科學必須了解讓計算機去解決問題在通用模型中的結構，由于要求在有限和有效時間內計算機自動完成，那么問題求解的方法必然是構造性的。

(2)從計算機科學學生能力角度培養的看計算理論的作用。計算機出現的五十多年間，人們追求著和出現了許多計算機信息革命帶來的信息產品，但是信息產品受工業產品的觀念上的影響，使得計算機科學的學科發展帶來了偏差，使得整個學科的發展都是“軟件跟著硬件走”。我們不能將自己的學生培養成計算機系統的奴隸，而應該培養成計算機系統的主人，我們的學生不能給計算機系統所塑造，將他們變成計算機，而是教育學生怎樣地塑造計算機系統。

在計算機科學知識掌握的過程中應是“硬件跟著軟件走，軟件跟著模型走，模型跟著學科實際應用走；學科實際應用跟著自然走”。而最主要的培養環節應該是軟件跟著模型走，模型跟著學科實際應用走。關于學生的培養目標就是要培養自己的學生能夠根據實際應用問題提出計算機應用的模型，并用硬件和軟件資源去構造計算機系統去完成模型中所提出來的工作。

首先，計算機系統要解決的問題并不是個別的問題，也并不是某個領域上的特殊問題，要解決某個領域的所有能用計算機進行計算的問題，因此，關于計算機科學的思維方法必須是在足夠通用的層面上的思維方法。如果所掌握或所習慣的思維方法僅限制在是某些特殊的領域，那么，隨著計算機應用的不斷擴大和計算機信息革命的不斷擴大，將會使得思維的方法帶有很大的局限性。當然，最通用的層面是自然層面，然而，自然層面上的對象還不能為現代計算機(現代計算模型)所了解。因為，我們選擇塑造計算機系統的層面既帶有最大的通用性，又能為現代計算機系統所了解的層面。在現代計算技術的支持下，這個層面就是符號處理層面。

其次，我們是要去塑造計算機系統，我們的所有思維都要立足于能“塑造”性，因此，思維的可構造性，即在考慮構成計算機系統的所有對象都必須能夠有某種方法在有限的時間內構造出來。因此塑造計算機系統的基本思維是構造性思維。以上描述了計算理論的學科定位下面我們來看相關的歷史人物簡介計算理論的開拓者—圖靈阿蘭·圖靈，1912年6月23日出生于英國倫敦。其祖父曾獲得劍橋大學數學榮譽學位，但他父親的數學才能平平。因此，圖靈的家庭教育，對他以后在數學及計算機方面的成就并沒有多少幫助。

小時侯的圖靈生性活潑好動，很早就表現出對科學的探索精神。據他母親回憶，3歲時，小圖靈就進行了他的首次實驗，嘗試把一個玩具木頭人的小胳膊、小腿掰下來栽到花園里，等待長出更多的木頭人。到了8歲，他更開始嘗試寫一部科學著作，題目為《關于一種顯微鏡》。在這部很短的書中，天才兒童圖靈拼錯了很多單詞，句法也有些問題，但寫得還能讓人看懂，很像那么一回事兒。在書的開頭和結尾，他都用同一句話“首先你必須知道光是直的”作前后呼應，但中間的內容卻很短，短得破了科學著作的記錄。圖靈曾說:“我似乎總想從最普通的東西中弄出些名堂。”就連和小朋友們玩足球，他也能放棄當前鋒進球這樣出風頭的事，只喜歡在場外巡邊，因為這樣能有機會去計算球飛出邊界的角度。他的老師認為:“圖靈的頭腦思維可以像袋鼠一樣進行跳躍。”圖靈是個天才。他16歲就開始研究愛因斯坦的相對論。1931年，圖靈考入劍橋大學國王學院，開始他的數學生涯，研究量子力學、概率論和邏輯學。在校期間，圖靈還是現代語言哲學大師維特根斯坦班上最出色的學生。他對由劍橋大學的羅素和懷特海創立的數理邏輯很感興趣。數理邏輯的創建，主要是為了對付“悖論”。“悖論”(paradox)是人類思維中最狡猾的兩面派，最早起源于古希臘克里特島上有個叫愛皮梅尼特的“智者”，他說:“所有的克里特島人都說謊”。我們可以把它簡化為:“我說的這句話是假話”。這就出現一種兩面都無法自圓的怪圈:如果他沒有說謊，那他這句話是錯的，他是在說謊;如果他真的在說謊，那他說自己在說謊是對的，所以他又沒有說謊。羅素和懷特海把它從邏輯、集合論以及數論中驅逐出去，最后又想盡辦法歸入《數學原理》之中。

圖靈一上大學，就迷上了《數學原理》。在1931年，著名的“哥德爾定理”出現后(該定理認為沒有一種公理系統可以導出數論中所有的真實命題，除非這種系統本身就有悖論)，天才的圖靈在數理邏輯大本營的劍橋大學提出一個設想:能否有這樣一臺機器，通過某種一般的機械步驟，能在原則上一個接一個地解決所有的數學問題。大學畢業后，圖靈去美國普林斯頓大學攻讀博士學位，還順手發明過一個解碼器。在那里，他遇見了馮·諾依曼，后者對他的論文擊節贊賞，并隨后由此提出了“存儲程序”概念。圖靈學成后又回到他的母校任教。在短短的時間里，圖靈就發表了幾篇很有份量的數學論文，為他贏得了很大的聲譽。

在劍橋，圖靈可稱得上是一個怪才，一舉一動常常出人意料。他是個單身漢和長跑運動員。在他的同事和學生中間，這位衣著隨便、不打領帶的著名教授，不善言辭，有些木訥、害羞，常咬指甲，但他更多地以自己杰出的才智贏得了人們的敬意。圖靈每天騎自行車上班，因為患過敏性鼻炎，一遇到花粉，就會鼻涕不止，大打噴嚏。于是，他就常常在上班途中戴防毒面具，招搖過市，這早已成為劍橋的一大奇觀。圖靈的自行車經常半路掉鏈子，但他就是不肯去車鋪修理。每次騎車時，他總是嘴里念念有詞，在心里細細計算，這鏈條也怪，總是轉到一定的圈數就滑落了，而圖靈竟然能夠做到在鏈條下滑前一剎那停車，讓旁觀者佩服不已，以為圖靈在玩雜技。后來圖靈又居然在腳踏車旁裝了一個小巧的機械記數器，到圈數時就停，歇口氣換換腦子，再重新運動起來。

1936年，圖靈向倫敦權威的數學雜志投了一篇論文，題為《論數字計算在決斷難題中的應用》。在這篇開創性的論文中，圖靈給“可計算性”下了一個嚴格的數學定義，并提出著名的“圖靈機”(TuringMachine)的設想。“圖靈機”不是一種具體的機器，而是一種思想模型，可制造一種十分簡單但運算能力極強的計算機裝置，用來計算所有能想像得到的可計算函數。裝置由一個控制器和一根假設兩端無界的工作帶(起存儲器的作用)組成。工作帶被劃分為大小相同的方格，每一格上可書寫一個給定字母表上的符號。控制器可以在帶上左右移動，它帶有一個讀寫頭，可讀出控制器所訪問的格子上的符號，也能改寫或抹去這一符號，最后便會得出一個你期待的結果。外行人看了會墜入云里霧里，而內行人則稱它是“闡明現代電腦原理的開山之作”，并冠以“理想計算機”的名稱。這篇論文在紙上談了一把兵，創造出一個“圖靈機”來。但現代通用電腦確實是用相應的程序來完成任何設定好的任務。這一理論奠定了整個現代計算機的理論基礎。“圖靈機”更在電腦史上與“馮·諾依曼機”齊名，被永遠載入計算機的發展史中。1931年，年輕的法國數學家赫爾布蘭德（JacquesHerbrand，1908～1931）對遞歸函數進行了研究，并給著名邏輯學家哥德爾（KurtG?del，1906～1978）寫信敘述了自己的研究結果。哥德爾當時正處于自己一生中最重大的成果—哥德爾不完全性定理的研究時期，他沒有仔細看赫爾布蘭德的來信內容，因此沒有立即對赫爾布蘭德的工作做出回應。那一年的夏天，年僅23歲的赫爾布蘭德在攀登阿爾卑斯山時不幸遇難，他的工作因此被暫時埋沒了。

與赫爾布蘭德的研究差不多同時，1931年秋天，普林斯頓大學的美國邏輯學家丘奇（AlonzoChurch，1903～1995）也在積極從事邏輯及算法的研究，并且發展出了一種新的邏輯體系。丘奇在普林斯頓開了一門邏輯課，他讓自己的兩個學生克林（StephenKleene，1909～1994）與羅瑟（JohnRosser，1907～1989）對這一體系做細致的研究。兩個學生都是一流好手，他們的研究很快就有了結果，但這結果大大出乎丘奇的意料。他們發現丘奇的那套體系竟然是自相矛盾的！命運似乎只有一個：放棄。幸運的是，丘奇的那套體系中有一個組成部分是自洽的，因此可以保留下來，這部分叫做蘭姆達運算（λ－calculus）。這種蘭姆達運算可以用來定義函數，而所有用蘭姆達運算定義的函數都是可以有效計算的。在對蘭姆達運算做了研究之后，丘奇提出了一個大膽的猜測，他猜測所有可以有效計算的函數都可以用蘭姆達運算來定義。于是克林開始進行研究，結果克林和丘奇得到一類可計算的函數，他們稱之為A可定義函數。

1934年春天，哥德爾在普林斯頓大學做了一系列講演。丘奇向到普林斯頓大學訪問的哥德爾介紹了他的猜測，哥德爾卻不以為然。丘奇不服氣，請哥德爾給出一個他認為合適的描述。一兩個月后，哥德爾就給出了一種完全不同的描述，這種描述的基礎正是3年前赫爾布蘭德在給他的信中敘述的結果。哥德爾對這一結果進行了完善，這一結果被人們稱為赫爾布蘭德－哥德爾遞歸函數。與此同時，丘奇和克林在1936年分別發表論文，證明A可定義函數類正好就是一般遞歸函數類。有了這個有力的證據，丘奇于是公開發表他的"論點"。這樣，丘奇與哥德爾各自給出了一種體系，描述可以有效計算的函數。丘奇與克林很快證明，這兩種看上去完全不同的描述方式實際上是彼此等價的。

兩位著名邏輯學家的工作殊途同歸，大大增強了丘奇的信心。他相信人們已經找到了可以有效計算的函數的普遍定義。但哥德爾及其他一些人對此卻仍然懷有疑慮。最終打消這種疑慮的是英國數學家圖靈（AlanTuring，1912～1954）。

1937年圖靈證明了用圖靈機可計算的函數類與可定義函數類是一致的，當然，也就和一般遞歸函數類相重合。這樣一來，丘奇的論點與圖林的論點就是一回事。當時許多人對于丘奇的論點表示懷疑，由于圖林的思想表述得如此清楚，從而消除了許多人的疑慮，哥德爾就是其中一位。從這時起大家對于丘奇-圖靈論點一般都抱支持的態度了。數理邏輯學家歌德爾

1947年美國數學家波斯特（EmilPost，1897～1954）找到了第一個邏輯領域以外的不可判定命題。波斯特是一位有著深刻洞察力的邏輯學家，7歲時隨父母從波蘭移民到美國，是美國邏輯學的先驅之一。他10年前就得到了與哥德爾不完全性定理相似的結果，由于想對結果作更全面的分析而沒有及時發表。他也是最早意識到希爾伯特第十問題可能會有否定答案的數學家之一。1944年，他在一篇文章中明確提出希爾伯特第十問題“期待一個不可解性證明”。當時波斯特在紐約市立大學任教，他的這一觀點深深打動了一位學生，使后者走上了畢生鉆研希爾伯特第十問題的征途。這位學生名叫戴維斯（MartinDavis，1928～），是解決希爾伯特第十問題的關鍵人物。圖靈獎與計算理論圖靈獎是由ACM于1966年首次設立的獎項,它是為了紀念“計算機科學之父”圖靈而設立的,專門獎勵那些在計算機科學研究中做出創造性貢獻、推動了計算機科學技術發展的杰出科學家。雖然沒有明確規定，但從實際執行過程來看，圖靈獎偏重于在計算機科學理論和軟件方面作出貢獻的科學家。獎金金額不算太高，設獎初期為2萬美元，1989年增至2萬5千美元，獎金通常由計算機界的一些大企業提供（通過與ACM簽定協議）。由于圖靈獎對獲獎者要求極高，評獎程序又極嚴，一般每年只獎勵一名計算機科學家，只有極少數年度有兩名合作者或在同一方向作出貢獻的科學家共享此獎。因此它是計算機界最負盛名、最崇高的一個獎項，有‘計算機界的諾貝爾獎“之稱。從1966年到2000年共有41位科學家獲此殊榮，在這些學者中從事計算復雜性理論研究的有11人，幾乎占四分之一。他們是？？？？1976年圖靈獎獲得者拉賓和斯科特1976年的圖靈獎由當時在以色列希伯萊大學的教授拉賓和英國牛津大學的數理邏輯教授斯科特共同獲得。他們是師兄弟，兩人在50年代中期先后師從于著名的數理邏輯與計算機科學家丘奇（他對可計算性理論做出了實質性貢獻，如判定問題的解、演算的發明，90歲還在發表論文，圖靈也是他的學生），并在有限自動機及其判定問題的研究中進行合作，奠定了非確定性有限自動機的理論基礎，之后，他們的研究方向不盡相同，拉賓側重于計算理論，而斯科特側重于邏輯學在計算機科學中的應用，在各自的領域中又分別獲得重大成果，做出了創造性貢獻。計算機科學家、數理邏輯學家丘奇拉賓是1931年出生于德國的布雷斯勞的猶太人，1948年以色列建國以后成為以色列公民，20世紀50年代拉賓博士畢業于普林斯頓大學，使拉賓成名的是IBM研究中心1957年向他和師弟斯科特提供的允許他們做自己感興趣的工作。于是他們二人聯手研究圖靈機----有限狀態自動機。他們定義了一種新的、“非確定性”行為的有限狀態自動機(NDFSA)，這種機器在讀去到一定的輸入后，有一個可以進入的可能的新的狀態的‘菜單’可供選擇，這樣對給定的輸入計算便不單一了，每個選擇代表一種可能的計算。拉賓和斯科特將圖靈的有限狀態自動機從確定性一種擴展到非確定的另一種形式，極大地推動了有限狀態自動機理論的發展，雖然非確定性有限狀態自動機的能力并不比確定性的有任何增加（拉賓和斯科特已經證明他們等價），但是它可以簡化機器描述和加快解題速度。后來的時間證明，非確定性有限狀態自動機在機器翻譯、文獻檢索和字處理程序等應用中都起到了重要作用。他們的研究結果發表于2年后的1959年IBM雜志上，題目為“有限自動機及其判定問題”。1958年夏天拉賓又來到IBM，當時“人工智能之父”麥卡錫（1971年圖靈獎獲得者）正在那里研究往巴克斯（1977年圖靈獎獲得者）發明的FORTRAN語言中加入表處理功能，他給拉賓出了一道難題：設計一種口令即使口令被敵方竊取，也無法進入系統。拉賓經過艱苦探索，終于利用馮諾伊曼開發的一個單向函數解決了這個問題。正是這個問題促使拉賓進一步研究計算任務的最小計算量這一一般性問題，也就是計算的固有難度問題，從而使拉賓成為最早研究計算復雜性問題的先驅之一。他的研究結果“計算速度和遞歸集合的分類”與“函數的計算難度和遞歸集合的偏序”分別于1959和1960年在耶路撒冷發表。論文中雖然沒有用“計算復雜性‘這個名詞而用了”計算速度“和”計算難度“，但學術界公認這兩篇論文是研究計算復雜性的最早、最權威的論文中的兩篇，對1964年正式提出”計算復雜性“這一術語的哈特馬尼斯和斯特恩斯（這2人是1993年圖靈獎獲得者，后面介紹）以及計算復雜性理論的另一奠基人布盧姆（1995年圖靈獎獲得者，后面介紹）都產生了深刻影響。其中布盧姆正是聽到了拉賓的有關演講才開始研究計算復雜性并完成博士論文的。斯科特比拉賓小一歲，1932年出生于加利福尼亞，在加州大學伯克利分校獲得學士學位后，進入普林斯頓大學研究生院深造，與拉賓一起師從于阿隆索丘齊。丘齊對學生要求很嚴，布置的問題也很難，斯科特開始時難以適應，精神很緊張，經常夜里作惡夢。但經過努力，終于可以從容應付。1957年他與師兄拉賓一起完成了對圖靈機的研究，提出了非確定性有限狀態自動機的理論以后，在1958年取得博士學位。之后他先后在芝加哥大學、加州大學伯克利分校、斯坦福大學、普林斯頓大學和牛津大學等國際知名高等學府任教。1981年被卡內基梅隆大學聘為計算機科學、數理邏輯和哲學教授。斯科特的主要興趣和研究方向是邏輯學，包括集合論、模型論、自動機理論、非經典邏輯中的模態邏輯和直覺主義邏輯。斯科特的最大貢獻是他與斯特雷奇合作，20世紀60年代提出了程序設計語言的“標志語義模型”為標志語義學奠定了堅實的基礎。1978年圖靈獎獲得者弗洛伊德歷屆圖靈獎得主基本上都有高學歷、高學位，絕大多數都有博士學位，但事情總有例外，1978年圖靈獎得主、斯坦福大學計算機科學系教授弗洛伊德就是一位“自學成才的計算機科學家”。說他自學成才并不是說他沒有接受過高等教育，他是芝加哥大學的畢業生，但學的是文學，1953年獲得文學學位，由于當時經濟不景氣，成為西屋電氣公司一名計算機操作員，他不懂計算機，但是個有心人，受過良好高等教育很快對計算機產生了興趣開始學習相關知識，1956年成為程序員，1965年被卡內基-梅隆大學聘為副教授，1970年聘為教授。大家現在熟知的優先文法，界限上下文文法都是他20世紀60年代提出的，優先文法解決了自底向上的語法分析中的首要問題：如何找到”句柄“，也就是當前需要歸約的符號串。1964年與威廉姆斯共同發明了堆排序算法HEAPSORT，這是與英國學者霍爾（1980年圖靈獎獲得者）發明的QUICKSORT齊名的高效排序算法之一。1982年圖靈獎獲得者庫克NP完全性理論的奠基人庫克1939年出生于紐約州的布法羅。1957年中學畢業后，到密歇根大學學科學工程，一年級時選擇了一門新開設的課程—程序設計，作為作業，他編了一個ALGOL程序驗證歌德巴赫猜想，由此他對計算機科學發生了興趣。1961年庫克獲得學士學位以后，轉入哈佛大學研究生院深造，第二年就取得了理科碩士學位，他接著攻讀了數學博士學位，原先打算研究代數學。然而這時他遇到了一些教師，對他產生了很大的影響，改變了他的興趣和方向。首先是哈佛研究生院對新興學科十分重視，雖然當時計算復雜性理論這一學科還處于萌芽和初創時期，他們就邀請了這方面的一些先驅與奠基人，包括拉賓、哈特馬尼斯和斯特恩斯，由于對拉賓等人講學或做報告內容產生興趣，庫克他們的研究和探索的問題發生了極大的興趣，從而把自己的研究定在這個方向。博士畢業后當時美籍華人數學家王浩提出的圖靈機的一種變形叫B機器也引起了他的興趣。王浩指出，甚至在無限的時間里，要想證明確定謂詞演算中的某個公式是否可滿足，在計算上都是不可能的，因此王浩從復雜性角度去研究，他的工作給了庫克極大的啟發，庫克從比較單純和簡單的命題演算公式的自動證明入手研究計算復雜性，果然成功了，１９７１年發表了“定理證明過程的復雜性”。在這篇論文中庫克首次明確提出了NP完全問題，并奠定了NP完全性理論的基礎。以后我們將講授這些內容。1985年圖靈獎獲得者卡普發明“分枝限界法”的三棲學者卡普是美國加州大學計算機、數學和工業工程三個系的教授，他被授予圖靈獎也是因為在算法設計與分析、計算復雜性理論等方面的創造性貢獻，生于１９３５年的卡普興趣廣泛聰明過人，在哈佛大學時文理兼修，1955年先獲得文學學士學位，第2年又獲得理科碩士學位，之后進入哈佛計算機實驗室攻讀博士學位，1959年獲得數學博士學位后進入IBM。

當時，正是計算機科學的創立時期，高級語言剛剛誕生不久，計算機應用開始被社會所重視并逐漸走向普及。有關數據結構、算法、計算復雜性等課題吸引著眾多學者的注意。IBM作為美國乃至世界最大的計算機廠商，理所當然成為這些研究問題的中心之一，集中了大批最優秀的研究人員，在那里卡普主要研究了路徑問題、背包問題、覆蓋問題、匹配問題，調度問題等，但這些問題都存在組合爆炸問題。２０世紀６０年代初卡普仔細研究了路徑問題中的旅行商問題，和同事海爾特經過反復研究，終于提出了一種稱為”分枝限界法“的新方法。該方法要點是：對解集合反復進行分枝，每次分枝時都對所得的子集計算最優解的界，如果對某個子集求得的界不優于已知的允許解，則拋棄這個子集不再分枝。否則繼續分枝以探索更好的解。１９６８年卡普來到加州大學伯克利分校。這里是計算機科學理論的又一個研究中心，庫克、布盧姆（１９８５年圖靈獎獲得者）等一批知名學者當時都在那里，學術氣氛十分濃厚。布盧姆是計算復雜性的主要奠基人之一，庫克則與1971年最早提出”NP完全性“問題，在這樣環境下，卡普對計算復雜性問題的研究日益深入。１９７２年卡普發表的論文“組合問題中的可歸約性”發展和加強了由庫克提出的”NP完全性”理論。尤其是庫克僅證明了命題演算的可滿足性問題是NP完全的，而卡普則證明了從組合優化中引出的大多數經典問題，包括背包問題、覆蓋問題、匹配問題、路徑問題、調度問題等，都是NP完全問題：只要證明其中任何一個問題是屬于P類的，就可以解決計算復雜性理論中的最大的一個難題P=?NP這是卡普論文的主要貢獻和意義。1986年圖靈獎獲得者霍普克洛夫斯特和陶爾揚霍普克洛夫斯特１９３９年出生于西雅圖，１９６１年西雅圖大學畢業后進入斯坦福大學研究生院深造，博士畢業后到普林斯頓大學工作。他成為著名的計算機科學家起源于一個十分偶然的機會。他學習的是電器工程專業，對計算機科學原本沒有多少知識。原打算到一所西海岸大學教授電器工程方面的課程。畢業前夕，有一次路過導師的辦公室門口，當時普林斯頓大學的麥克盧斯基正為籌建”數字需要實驗室“給霍普克洛夫斯特的老師打電話讓推薦博士，他的老師一眼瞥見了他，覺得勤奮好學、悟性又高的得意門生正是值得推薦的人才，就把他叫進來并把話筒遞給他，經過交談與考察，他接受了普林斯頓大學的邀請，從而改變了一生的道路。

年輕的霍普克洛夫斯特到普林斯頓之后接受的第1個任務是開設一門新課程：自動機理論，這對他來說是富有挑戰性的，因為他之前并沒有接觸過這個課程。面對挑戰，他虛心地請麥克盧斯基推薦關有參考資料。由于當時沒有任何一所學校開設過自動機理論的課程，也沒有一本書籍，到底應該講什么心里也沒有底。通過大量翻閱文獻，他開設了包括圖靈、麥柯勞赫和皮孜、拉賓和斯科特、巴克斯和諾爾、哈特馬尼斯和斯特恩斯以及喬姆斯基所寫的6篇論文課程。他對圖靈的計算模型，麥柯勞赫和皮孜的神經網絡，拉賓和斯科特的有限自動機，巴克斯和諾爾描述程序的BNF，喬姆斯基的上下文無關文法等進行了深入專研與消化，并加以分析、綜合和比較，逐漸理出了頭緒，成功地開出了新課。后來與厄爾曼合作編寫了《形式語言及其與自動機的關系》，感興趣的同學可以作為參考書閱讀。１９７０年霍普克洛夫斯特和陶爾揚合作提出了深度優先算法等一些圖論中的難題而獲圖靈獎。陶爾揚1948年生于加利福尼亞，從小就是一個富于幻想、追求新鮮事物的人，幼年夢想成為登上火星的人，小學7年級開始看《科學美國人》雜志。1964年，陶爾揚參加了一個中學生夏令營，第一次接觸了計算機，立即被神奇的計算機所吸引，因此他上加州理工學院時，輔修了學校開設的所有計算機課程，1969年畢業后進入斯坦福大學師從于著名的計算機科學家克納斯(Knuth，1974年圖靈獎得主)，1970年在克納斯的有意安排下與康乃爾大學到普林斯頓學術休假的霍普克洛夫斯特共同研究圖論的算法。這個課題實際上是”人工智能之父“麥卡錫的建議下進行的，霍普克洛夫斯特的新思路