スティーブン・クック
活動期 1939年頃, アメリカ合衆国ニューヨーク州バッファロー
数学の基礎応用数学と計算数学
NP完全性理論を創始し、P対NP問題を定式化してクック・レビンの定理を証明したアメリカ・カナダの計算機科学者・数学者。
スティーブン・クックはニューヨーク州バッファローで生まれ、1966年にハーバード大学で数学の博士号を取得した。カリフォルニア大学バークレー校で助教授を務めた後、1970年にトロント大学に着任し、以後生涯そこで研究を続け、カナダ市民権を取得した。
1971年の論文「The Complexity of Theorem-Proving Procedures」でクックはNP完全性の概念を導入し、充足可能性問題(SAT)がNP完全であることを証明した——これがクック・レビンの定理であり、ソビエト連邦のレオニード・レヴィンも独立に発見した。この論文はP対NP問題の定式化でもあった:解の検証が速くできる問題はすべて速く解けるのか、という問いである。これにより計算複雑性理論という分野が誕生し、今なおクレイ・ミレニアム問題の一つとして未解決である。
この業績によりクックは1982年にACMチューリング賞を受賞した。計算機科学における最高の栄誉である。彼はその後もトロント大学で複雑性理論と証明の複雑性の研究を続け、現在は名誉教授である。
所属先: カリフォルニア大学バークレー校, トロント大学
カナダ, アメリカ合衆国