史提芬·古克

基本介紹

• 中文名：史提芬·古克
• 外文名：Stephen A. Cook
• 職業：計算機科學家

成果

1971年，在他的論文The Complexity of Theorem Proving Procedures，他整理了NP完備性的目標，亦產生了古克定理——布爾可滿足性問題是NP完備的證明。 1982年，古克得到圖靈獎。因為其論文開啟了NP完備性的研究，令這個範疇於之後的十年成為計算機科學中最活躍和重要的研究。

史提芬·古克

加拿大多倫多大學教授史蒂芬·庫克(Stephen Arthur Cook)因在計算複雜性理論方面的貢獻，尤其是在奠定NP完全性理論基礎上的突出貢獻而榮獲1982年度的圖靈獎。

背景

史提芬·古克是美國科學家，1939年12月14日生於紐約州的布法羅(Buffalo)，他的父親是一名化學家，在著名的聯合碳化物公司工作，同時在布法羅大學任教，有一份不錯的收入。但庫克的父親喜歡農村的恬靜生活和清新空氣，因此在庫克10歲時全家遷居到紐約州克拉倫斯的一個奶牛場。在這裡，少年庫克可以與牛羊為伴，還學會了擠奶。在鄉村中學，庫克的數學成績比較好，但那時他並沒有夢想當數學家。庫克的另一個愛好是下棋，這幫助他發展了邏輯思維能力。在克拉克倫斯，當時出現了一位傳奇式的英雄，那就是威爾遜·格萊特巴郝(Wilson Greatbatch)，他發明了可植入式心臟起搏器，挽救了世界上無數人的性命，使他遠近聞名。庫克對這位發明家也很敬仰和崇拜，暑假時曾到他手下去打工，幫他焊電晶體電路板。當時電晶體問世不久，是新鮮事物，庫克對神奇的電晶體也很有興趣，想當個電氣工程師。

歷程

1957年中學畢業後，庫克離開克拉倫斯去上密西根大學，專業是科學工程。一年級時他選了一門新開設的課程——程式設計，第一次接觸計算機。作為作業，他編了一個Algol程式以驗證哥德巴赫猜想，在機器允許的範圍內，每個大於3的偶數都是2個素數之和。這使庫克開始對計算機科學發生興趣。1961年庫克獲得學士學位以後，轉入哈佛大學研究生院深造，第二年就取得了理科碩士學位。他接著攻讀數學博士學位，原先的打算是研究代數學。 然而這時他遇到了一些教師，對他產生了很大的影響，改變了他的興趣和方向。首先是哈佛研究生院對新興學科十分重視，雖然計算複雜性理論這一學科分支其時還處於萌芽與初創時期，它就邀請了這方面的一些先驅與奠基人，其中包括拉賓(M．Rabin，1976年圖靈獎獲得者)、哈特馬尼斯(J．Hartmanis)和斯坦恩斯(R．Steams，這兩人是1993年圖靈獎獲得者)等人前來講學或作報告。庫克對他們所研究和探索的問題產生了極大的興趣，從而把自己的研究也定在了這個方向。

史提芬·古克

他的博士論文“論乘法的最小計算時間”(On the Minimum Computation Time for Multiplication)就是他涉足這一領域的初步嘗試。但這個課題局跟性太大，無法從中找出一般規律。這時，在哈佛大學套用科學研究所任教的美籍華人學者王浩的研究工作引起了庫克的注意和啟發了他。王浩是國際知名的數理邏輯專家和計算機科學家，他曾對圖靈的計算理論進行深入研究並提出了圖靈機的一種變形叫B機器(Bmachine)。B機器的特點是總共只有4條指令，機器不能自我修改，即不能抹去帶上的記號。B機器比圖靈機更加接近於實際機器，它能計算的函式正好是部分遞歸函式。

當時王浩正致力於研究自動定理證明，即由計算機自己去證明定理，具體而言是證明謂詞演算中的定理，這就涉及到可滿足性問題(Satisfiable)，即是否存在一個真假值的賦值，使得給定的公式成立。如果存在，那末就稱這個公式是可滿足的，否則就是不可滿足的。一般謂詞演算公式的可滿足性問題，圖靈早就解決了，他指出，甚至在無限的時間裡，要想確定謂詞演算中的某個公式是否可滿足，在計算上都是不可能的。因此，王浩是從複雜性的角度去研究謂詞演算的可滿足性的。王浩的研究工作給了庫克以極大的啟發，他認識到，自動定理證明可以作為研究計算複雜性問題的一個很好的突破口。但是由於謂詞演算涉及個體與群體，公式中包含所謂量詞(quantifier)，即全稱量詞d1(universal quantifier，用“∨”表示)和存在量詞exists(existential quantifier，用“∧”表示)，使研究變得複雜而困難。

因此庫克改從比較單純和簡單的命題演算公式的自動證明人手研究計算複雜性，果然獲得成功：1971年5月，他在ACM於俄亥俄州的Shaker Heights舉行的第三屆計算理論研討會上發表了那篇著名的論文：“定理證明過程的複雜性”(The Complexity of Theorem Proving Procedures)，在這篇論文中，庫克首次明確提出了NP完全性問題，並奠定了NP完全性理論的基礎。所謂“NP完全性”(NP- completeness)問題是這樣一個問題：由於P二?NP問題難以解決，庫克就另闢途徑，從NP類的問題中分出複雜性最高的一個子類，把它叫做NP 完全類。庫克證明，任取NP類中的一個問題，再任取NP完全類中的一個問題，則一定存在一個確定性圖靈機上的具有多項式時間複雜性的算法，可以把前者轉變成後者。這就表明，只要能證明NP完全類中有一個問題是屬於P類的，也就證明了NP類中的所有問題都是P類的，即證明了P=NP。庫克的這一研究成果為研究P=?NP的科學家們指明了一條捷徑和一個方向，不必再像大海撈針似地去盲目探索了。

雖然科學家們沿著庫克指明的這條“捷徑”仍在艱難地前進，至今沒有達到光輝的終點(P=?NP的問題至今仍未有結論)，但學術界公認庫克的NP完全性理論是對計算複雜性理論的一個重大貢獻。庫克的論文只證明了命題演算的可滿足性問題是NP完全的，但在它的啟發下，卡普(R．Karp，1985年圖靈獎獲得者)在第二年就證明了21個有關組合最佳化的問題也是 NP完全的，從而加強與發展了NP完全性理論。 庫克在建立NP完全性理論時，為研究複雜性類之間的關係提出的方法，叫“複雜性歸約”(complexity reduction)，用以比較問題的計算難度。庫克所用的歸約方法是多項式時間圖靈歸約，有時直接把它叫做庫克歸約。其要點如下：假設所考慮的問題都已編碼成字母表∑上的語言(實例的集合)。設Ll、L2是∑上的兩個語言，若存在以上：為oracle集的多項式時間圖靈機M，其接受的語言為Ll，則稱 L1，多項式時間圖靈歸約到L2，記為i1≤PTL2。這時，對x是否屬於L1的判別可轉化為至多，|x|的多項式個元素是否屬於i2的判別，因此 L2∈p便導致L1∈p。從這種相對的意義上說，i1的計算不比L2難。≤；可以是定義在任何語言類D上的一種二元前序關係，如果存在L∈D，對於任何 L'∈D，都有L'≤PtL，則L就是D中(在多項式時間圖靈歸約下)“最困難的”，稱其為D-T完全的。

史提芬·古克

在庫克歸約的基礎上，其他計算機科學家又用其他各種計算模型定義了其他一些複雜性歸約，如多一歸約、對數空間歸約、Y-歸約、隨機歸約和真值表歸約等。但庫克歸約仍然是最常用的歸約方法之一。複雜性歸約除了用於判定問題外，還可以用於函式和搜尋問題。

庫克取得博士學位以後，在加州大學伯克利分校工作了幾年，1970年轉至多倫多大學。

圖靈獎演說

向庫克頒發圖靈獎的儀式是1982年10月25日在達拉斯舉行的ACM年會上進行的。庫克發表了題為“計算複雜性綜述”(An Overview of Computational Complexity)的圖靈獎演說，演說全面而系統地回顧了計算複雜性理論從萌芽到發展到成熟所走過的歷程以及面臨的新的挑戰。