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

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

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

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

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

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

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

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

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

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

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

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