計算復(fù)雜性課件

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

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

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

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

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

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

第三個重大問題（整個學科綜述性導(dǎo)引課程的構(gòu)建）的解決，將使人們對整個學科的認知科學化、系統(tǒng)化和邏輯化。如果人們對計算學科的認知能建立在公理化的基礎(chǔ)之上，則該學科可被認為是嚴謹?shù)目茖W、成熟的學科，從而有助于它的發(fā)展，并將由此而得到人們的尊重。

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

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

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

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

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

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

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

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

在計算機科學知識掌握的過程中應(yīng)是“硬件跟著軟件走，軟件跟著模型走，模型跟著學科實際應(yīng)用走；學科實際應(yīng)用跟著自然走”。而最主要的培養(yǎng)環(huán)節(jié)應(yīng)該是軟件跟著模型走，模型跟著學科實際應(yīng)用走。關(guān)于學生的培養(yǎng)目標就是要培養(yǎng)自己的學生能夠根據(jù)實際應(yīng)用問題提出計算機應(yīng)用的模型，并用硬件和軟件資源去構(gòu)造計算機系統(tǒng)去完成模型中所提出來的工作。

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

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

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

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

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

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

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

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

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

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

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

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

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