スティーブン・クック
博士課程では、関数、特に乗法の複雑性を研究。1966年に博士号を取得した。数年後の1971年の論文 "The Complexity of Theorem Proving Procedures"(定理証明手続きの複雑性)で、多項式時間変換(チューリング還元)の記法とNP完全性を定式化し、充足可能性問題 (SAT) がNP完全だと示すことでNP完全問題の存在を証明した。特に後者の件はソビエト連邦のレオニード・レビン(英語版)も独自に発見しており、クック-レビンの定理(英語版)と呼ばれている。その論文では計算機科学最大の問題である「P対NP問題」も定式化している。「P対NP問題」は非形式的には、答えの正しさや最適さを効率的に確認できるあらゆる最適化問題について効率的アルゴリズムで最適に解くことができるかどうか、という問題である。日常生活におけるそのような最適化問題は豊富に存在するので、「P対NP問題」への肯定的な答えが得られれば、実用的にも哲学的にも意義深い結果となる。
クックは、(容易に解を検証可能な)最適化問題の中に効率的アルゴリズムで解けないものがある、すなわち P と NP は等しくないと予想した。この予想は計算複雑性理論の研究を活発化させ、それによって計算問題の本質的複雑性への理解が深まり、効率的に計算できる問題についても理解が深まった。クックのP≠NP予想は今も証明されておらず、有名な7つのミレニアム懸賞問題の1つとされている。
その計算複雑性理論への多大な貢献により、82年のチューリング賞を受賞。 受賞理由は次の通り。