史提芬·古克 - 簡介

史提芬·A·古克(Stephen A. Cook)是計(jì)算機(jī)科學(xué)家，計(jì)算復(fù)雜性理論的重要研究者。古克現(xiàn)為多倫多大學(xué)的計(jì)算機(jī)科學(xué)和數(shù)學(xué)部門教授。 

史提芬·古克 - 成果

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

1982年，古克得到圖靈獎(jiǎng)。因?yàn)槠湔撐拈_啟了NP完備性的研究，令這個(gè)范疇于之后的十年成為計(jì)算機(jī)科學(xué)中最活躍和重要的研究。

加拿大多倫多大學(xué)教授斯蒂芬·庫克(Stephen Arthur Cook)因在計(jì)算復(fù)雜性理論方面的貢獻(xiàn)，尤其是在奠定NP完全性理論基礎(chǔ)上的突出貢獻(xiàn)而榮獲1982年度的圖靈獎(jiǎng)。

史提芬·古克 - 背景

史提芬·古克是美國科學(xué)家，1939年12月14日生于紐約州的布法羅(Buffalo)，他的父親是一名化學(xué)家，在著名的聯(lián)合碳化物公司工作，同時(shí)在布法羅大學(xué)任教，有一份不錯(cuò)的收入。但庫克的父親喜歡農(nóng)村的恬靜生活和清新空氣，因此在庫克10歲時(shí)全家遷居到紐約州克拉倫斯的一個(gè)奶牛場。在這里，少年庫克可以與牛羊?yàn)榘�，還學(xué)會(huì)了擠奶。在鄉(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年圖靈獎(jiǎng)獲得者)、哈特馬尼斯(J．Hartmanis)和斯坦恩斯(R．Steams，這兩人是1993年圖靈獎(jiǎng)獲得者)等人前來講學(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í)王浩正致力于研究自動(dòng)定理證明，即由計(jì)算機(jī)自己去證明定理，具體而言是證明謂詞演算中的定理，這就涉及到可滿足性問題(Satisfiable)，即是否存在一個(gè)真假值的賦值，使得給定的公式成立。如果存在，那末就稱這個(gè)公式是可滿足的，否則就是不可滿足的。一般謂詞演算公式的可滿足性問題，圖靈早就解決了，他指出，甚至在無限的時(shí)間里，要想確定謂詞演算中的某個(gè)公式是否可滿足，在計(jì)算上都是不可能的。因此，王浩是從復(fù)雜性的角度去研究謂詞演算的可滿足性的。王浩的研究工作給了庫克以極大的啟發(fā)，他認(rèn)識到，自動(dòng)定理證明可以作為研究計(jì)算復(fù)雜性問題的一個(gè)很好的突破口。但是由于謂詞演算涉及個(gè)體與群體，公式中包含所謂量詞(quantifier)，即全稱量詞d1(universal quantifier，用“∨”表示)和存在量詞exists(existential quantifier，用“∧”表示)，使研究變得復(fù)雜而困難。

因此庫克改從比較單純和簡單的命題演算公式的自動(dòng)證明人手研究計(jì)算復(fù)雜性，果然獲得成功：1971年5月，他在ACM于俄亥俄州的Shaker Heights舉行的第三屆計(jì)算理論研討會(huì)上發(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)频厝ッつ刻剿髁恕?br>
雖然科學(xué)家們沿著庫克指明的這條“捷徑”仍在艱難地前進(jìn)，至今沒有達(dá)到光輝的終點(diǎn)(P=?NP的問題至今仍未有結(jié)論)，但學(xué)術(shù)界公認(rèn)庫克的NP完全性理論是對計(jì)算復(fù)雜性理論的一個(gè)重大貢獻(xiàn)。庫克的論文只證明了命題演算的可滿足性問題是NP完全的，但在它的啟發(fā)下，卡普(R．Karp，1985年圖靈獎(jiǎng)獲得者)在第二年就證明了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ù)和搜索問題。

庫克取得博士學(xué)位以后，在加州大學(xué)伯克利分校工作了幾年，1970年轉(zhuǎn)至多倫多大學(xué)。

史提芬·古克 - 圖靈獎(jiǎng)演說

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