斯蒂芬·庫克（1939年12月14日-），男，出生于紐約州的布法羅，是美國計算機科學家、計算復雜性理論的重要研究者，現為多倫多大學的計算機科學和數學系教授。庫克于1961年畢業于密歇根大學科學工程工程專業，并于1962年和1966年獲得哈佛大學碩士及博士學位。庫克在1971年發表的論文中整理了NP完備性的目標，并產生了庫克定理——布爾可滿足性問題是NP完備的證明，因此獲得1982年圖靈獎。
人物介紹
NP完全性理論的奠基人 斯蒂芬·A·庫克（Stephen A. Cook，1939年－），計算機科學家，計算復雜性理論的重要研究者。
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 時間 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-歸約、隨機歸約和真值表歸約等。但庫克歸約仍然是最常用的歸約方法之一。復雜性歸約除了用于判定問題外，還可以用于函數和搜索問題。
頒獎相關
向庫克頒發圖靈獎的儀式是1982年10月25日在達拉斯舉行的ACM年會上進行的。庫克發表了題為“計算復雜性綜述”(An Overview of Computational Complexity)的圖靈獎演說，演說全面而系統地回顧了計算復雜性理論從萌芽到發展到成熟所走過的歷程以及面臨的新的挑戰，還給出了上百篇有價值的參考文獻，值得關心這一學科的人細細閱讀。演說全文刊載于1983年6月的Communications of ACM，400-408頁，也可見《前20年的ACM圖靈獎演說集》(ACM Turing Award Lectures ——The First 20 Years：1966—1985，ACM h．411-432頁。)
參考資料 >