スティーブン・クック
重要かつ意義深い方法で我々の計算複雑性への理解を高めさせた貢献に対して。彼の重要な論文 The Complexity of Theorem Proving Procedures は1971年 ACM SIGACT 計算理論シンポジウムで発表され、NP完全性の理論の基礎となった。過去10年間、この領域は計算機科学の中でも最も活発な研究の場となった。
1975年に発表した論文 "Feasibly Constructive Proofs and the Propositional Calculus"で、多項式時間の概念のみを使った証明の記述を定式化するPV (Polynomial-time Verifiable) 方程式理論を提唱。1979年には指導学生 Robert A. Reckhow と連名の論文 "The Relative Efficiency of Propositional Proof Systems"では、p-simulation と効率的な命題証明系(英語版)の記法を定式化し、そこから命題論理証明複雑性(英語版)と呼ばれる分野が生まれた。彼らは「あらゆる真の論理式について短い証明がある証明系の存在」と NP = coNP が等価であることを証明した。クックはこの分野について指導学生 Phuong The Nguyen と共同で "Logical Foundations of Proof Complexity" という本を執筆している。
クックの主な研究領域は計算複雑性理論と証明複雑性(英語版)であり、プログラム意味論、並列計算、人工知能にも関心を寄せている。