NP完全性理論的奠基人史提芬·A·古克（Stephen A. Cook，1939年－），計(jì)算機(jī)科學(xué)家，計(jì)算復(fù)雜性理論的重要研究者。

1971年，在他的論文《The Complexity of Theorem Proving Procedures》，他整理了NP完備性的目標(biāo)，亦產(chǎn)生了古克定理——布爾可滿足性問題是NP完備的證明。

1982年，古克得到圖靈獎。因?yàn)槠湔撐拈_啟了NP完備性的研究，令這個(gè)領(lǐng)域于之后的十年成為計(jì)算機(jī)科學(xué)中最活躍和重要的研究�？爽F(xiàn)為多倫多大學(xué)的計(jì)算機(jī)科學(xué)和數(shù)學(xué)系教授。加拿大多倫多大學(xué)教授斯蒂芬·庫克(Stephen Arthur Cook)因在計(jì)算復(fù)雜性理論方面的貢獻(xiàn)，尤其是在奠定NP完全性理論基礎(chǔ)上的突出貢獻(xiàn)而榮獲1982年度的圖靈獎。

斯蒂芬·庫克實(shí)際上是美國科學(xué)家，1939年12月14日生于紐約州的布法羅(Buffalo)，他的父親是一名

化學(xué)家，在著名的聯(lián)合碳化物公司工作，同時(shí)在布法羅大學(xué)任教，有一份不錯(cuò)的收入。但庫克的父親喜歡農(nóng)村的恬靜生活和清新空氣，因此在庫克10歲時(shí)全家遷居到紐約州克拉倫斯的一個(gè)奶牛場。在這里，少年庫克可以與牛羊?yàn)榘�，還學(xué)會了擠奶。在鄉(xiāng)村中學(xué)，庫克的數(shù)學(xué)成績比較好，但那時(shí)他并沒有夢想當(dāng)數(shù)學(xué)家。庫克的另一個(gè)愛好是下棋，這幫助他發(fā)展了邏輯思維能力。在克拉克倫斯，當(dāng)時(shí)出現(xiàn)了一位傳奇式的英雄，那就是威爾遜·格萊特巴郝(Wilson Greatbatch)，他發(fā)明了可植入式心臟起搏器，挽救了世界上無數(shù)人的性命，使他遠(yuǎn)近聞名。庫克對這位發(fā)明家也很敬仰和崇拜，暑假時(shí)曾到他手下去打工，幫他焊晶體管電路板。當(dāng)時(shí)晶體管問世不久，是新鮮事物，庫克對神奇的晶體管也很有興趣，想當(dāng)個(gè)電氣工程師。

1957年中學(xué)畢業(yè)后，庫克離開克拉倫斯去上密歇根大學(xué)，專業(yè)是科學(xué)工程。一年級時(shí)他選了一門新開設(shè)的課程——程序設(shè)計(jì)，第一次接觸計(jì)算機(jī)。作為作業(yè)，他編了一個(gè)Algol程序以驗(yàn)證哥德巴赫猜想，在機(jī)器允許的范圍內(nèi)，每個(gè)大于3的偶數(shù)都是2個(gè)素?cái)?shù)之和。這使庫克開始對計(jì)算機(jī)科學(xué)發(fā)生興趣。

1961年庫克獲得學(xué)士學(xué)位以后，轉(zhuǎn)入哈佛大學(xué)研究生院深造，第二年就取得了理科碩士學(xué)位。他接著攻讀數(shù)學(xué)博士學(xué)位，原先的打算是研究代數(shù)學(xué)。然而這時(shí)他遇到了一些教師，對他產(chǎn)生了很大的影響，改變了他的興趣和方向。首先是哈佛研究生院對新興學(xué)科十分重視，雖然計(jì)算復(fù)雜性理論這一學(xué)科分支其時(shí)還處于萌芽與初創(chuàng)時(shí)期，它就邀請了這方面的一些先驅(qū)與奠基人，其中包括拉賓(M．Rabin，1976年圖靈獎獲得者)、哈特馬尼斯(J．Hartmanis)和斯坦恩斯(R．Steams，這兩人是1993年圖靈獎獲得者)等人前來講學(xué)或作報(bào)告。庫克對他們所研究和探索的問題產(chǎn)生了極大的興趣，從而把自己的研究也定在了這個(gè)方向。他的博士論文“論乘法的最小計(jì)算時(shí)間”(On the Minimum Computation Time for Multiplication)就是他涉足這一領(lǐng)域的初步嘗試。但這個(gè)課題局跟性太大，無法從中找出一般規(guī)律。這時(shí)，在哈佛大學(xué)應(yīng)用科學(xué)研究所任教的美籍華人學(xué)者王浩的研究工作引起了庫克的注意和啟發(fā)了他。王浩是國際知名的數(shù)理邏輯專家和計(jì)算機(jī)科學(xué)家，他曾對圖靈的計(jì)算理論進(jìn)行深入研究并提出了圖靈機(jī)的一種變形叫B機(jī)器(Bmachine)。B機(jī)器的特點(diǎn)是總共只有4條指令，機(jī)器不能自我修改，即不能抹去帶上的記號。B機(jī)器比圖靈機(jī)更加接近于實(shí)際機(jī)器，它能計(jì)算的函數(shù)正好是部分遞歸函數(shù)。當(dāng)時(shí)王浩正致力于研究自動定理證明，即由計(jì)算機(jī)自己去證明定理，具體而言是證明謂詞演算中的定理，這就涉及到可滿足性問題(Satisfiable)，即是否存在一個(gè)真假值的賦值，使得給定的公式成立。如果存在，那么就稱這個(gè)公式是可滿足的，否則就是不可滿足的。一般謂詞演算公式的可滿足性問題，圖靈早就解決了，他指出，甚至在無限的時(shí)間里，要想確定謂詞演算中的某個(gè)公式是否可滿足，在計(jì)算上都是不可能的。因此，王浩是從復(fù)雜性的角度去研究謂詞演算的可滿足性的。

王浩的研究工作給了庫克以極大的啟發(fā)，他認(rèn)識到，自動定理證明可以作為研究計(jì)算復(fù)雜性問題的一個(gè)很好的突破口。但是由于謂詞演算涉及個(gè)體與群體，公式中包含所謂量詞(quantifier)，即全稱量詞d1(universal quantifier，用“∨”表示)和存在量詞exists(existential quantifier，用“∧”表示)，使研究變得復(fù)雜而困難。因此庫克改從比較單純和簡單的命題演算公式的自動證明人手研究計(jì)算復(fù)雜性，果然獲得成功。

1971年5月，他在ACM于俄亥俄州的Shaker Heights舉行的第三屆計(jì)算理論研討會上發(fā)表了那篇著名的論文：“定理證明過程的復(fù)雜性”(The Complexity of Theorem Proving Procedures)，在這篇論文中，庫克首次明確提出了NP完全性問題，并奠定了NP完全性理論的基礎(chǔ)。所謂“NP完全性”(NP-completeness)問題是這樣一個(gè)問題：由于P二?NP問題難以解決，庫克就另辟途徑，從NP類的問題中分出復(fù)雜性最高的一個(gè)子類，把它叫做NP完全類。庫克證明，任取NP類中的一個(gè)問題，再任取NP完全類中的一個(gè)問題，則一定存在一個(gè)確定性圖靈機(jī)上的具有多項(xiàng)式時(shí)間復(fù)雜性的算法，可以把前者轉(zhuǎn)變成后者。這就表明，只要能證明NP完全類中有一個(gè)問題是屬于P類的，也就證明了NP類中的所有問題都是P類的，即證明了P=NP。庫克的這一研究成果為研究P=?NP的科學(xué)家們指明了一條捷徑和一個(gè)方向，不必再像大海撈針?biāo)频厝ッつ刻剿髁�。雖然科學(xué)家們沿著庫克指明的這條“捷徑”仍在艱難地前進(jìn)，至今沒有達(dá)到光輝的終點(diǎn)(P=?NP的問題至今仍未有結(jié)論)，但學(xué)術(shù)界公認(rèn)庫克的NP完全性理論是對計(jì)算復(fù)雜性理論的一個(gè)重大貢獻(xiàn)。庫克的論文只證明了命題演算的可滿足性問題是NP完全的，但在它的啟發(fā)下，卡普(R．Karp，1985年圖靈獎獲得者)在第二年就證明了21個(gè)有關(guān)組合優(yōu)化的問題也是NP完全的，從而加強(qiáng)與發(fā)展了NP完全性理論。

庫克在建立NP完全性理論時(shí)，為研究復(fù)雜性類之間的關(guān)系提出的方法，叫“復(fù)雜性歸約”(complexity reduction)，用以比較問題的計(jì)算難度。庫克所用的歸約方法是多項(xiàng)式時(shí)間圖靈歸約，有時(shí)直接把它叫做庫克歸約。其要點(diǎn)如下：假設(shè)所考慮的問題都已編碼成字母表∑上的語言(實(shí)例的集合)。設(shè)Ll、L2是∑上的兩個(gè)語言，若存在以上：為oracle集的多項(xiàng)式時(shí)間圖靈機(jī)M，其接受的語言為Ll，則稱L1，多項(xiàng)式時(shí)間圖靈歸約到L2，記為i1≤PTL2。這時(shí)，對x是否屬于L1的判別可轉(zhuǎn)化為至多，|x|的多項(xiàng)式個(gè)元素是否屬于i2的判別，因此L2∈p便導(dǎo)致L1∈p。從這種相對的意義上說，i1的計(jì)算不比L2難�！埽豢梢允嵌�義在任何語言類D上的一種二元前序關(guān)系，如果存在L∈D，對于任何L’∈D，都有L’≤PtL，則L就是D中(在多項(xiàng)式時(shí)間圖靈歸約下)“最困難的”，稱其為D-T完全的。

在庫克歸約的基礎(chǔ)上，其他計(jì)算機(jī)科學(xué)家又用其他各種計(jì)算模型定義了其他一些復(fù)雜性歸約，如多一歸約、對數(shù)空間歸約、Y-歸約、隨機(jī)歸約和真值表歸約等。但庫克歸約仍然是最常用的歸約方法之一。復(fù)雜性歸約除了用于判定問題外，還可以用于函數(shù)和搜索問題。

向庫克頒發(fā)圖靈獎的儀式是1982年10月25日在達(dá)拉斯舉行的ACM年會上進(jìn)行的。庫克發(fā)表了題為“計(jì)算復(fù)雜性綜述”(An Overview of Computational Complexity)的圖靈獎演說，演說全面而系統(tǒng)地回顧了計(jì)算復(fù)雜性理論從萌芽到發(fā)展到成熟所走過的歷程以及面臨的新的挑戰(zhàn)，還給出了上百篇有價(jià)值的參考文獻(xiàn)，值得關(guān)心這一學(xué)科的人細(xì)細(xì)閱讀。演說全文刊載于1983年6月的Communications of ACM，400-408頁，也可見《前20年的ACM圖靈獎演說集》(ACM Turing Award Lectures ——The First 20 Years：1966—1985，ACM h．411-432頁。)