1971年の論文「The Complexity of Theorem Proving Procedures」は、計算機科学における今日でも未解決の核心的な問題であるP versus NP問題の形式的基礎を築きました。スティーブン・クック（Stephen Cook）によって書かれたこの論文は、NP完全性の概念を導入し、数学者や計算機科学者が計算タスクの本質的な難しさを分類する方法を変えました。
学歴
1939年にバッファローで生まれたクックは、米国で高等教育を受けました。1961年にミシガン大学で学士号を取得し、その後1962年と1966年にそれぞれハーバード大学で修士号と理学博士号を取得しました。1966年にカリフォルニア大学バークレー校の助教授として教育キャリアを開始しました。1970年に同校を去った後、トロント大学に加わり、計算機科学科および数学科で務め、最終的に特任教授（Distinguished Professor）となりました。
計算複雑性
クックの研究は主に複雑性理論と証明の複雑さに焦点を当てています。ブール満充可能性問題（SAT問題）に関する彼の画期的な研究は、この問題がNP完全であることを示しました。この発見はレオニード・レヴィン（Leonid Levin）によって独立に導かれ、現在はクック・レヴィンの定理として知られています。彼の貢献には、複雑性クラスNC、SC、AC0の定義も含まれます。複雑性のほかにも、並行計算、プログラミング言語のセマンティクス、有界算術を研究しています。
専門的称賛
彼の業績は、計算複雑性の理解を前進させた功績により、1982年のACMアチューリング賞をはじめとする数々の国際的な栄誉を獲得しています。彼は計算機学会（Association for Computing Machinery）のフェローであり、王立協会、全米科学アカデミー、アメリカ芸術科学アカデミーなどの権威ある機関の会員です。カナダでは、2012年にハワード・ハワード・ヘルツバーグ科学・工学カナダ金メダルを受賞し、2015年にカナダ勲章オフィサーに任命されました。
クイックファクト
- 生誕：1939年、バッファロー - 国籍：カナダおよび米国 - チューリング賞：1982年 - 学位：理学博士 - 主な所属：トロント大学 - 主な栄誉：カナダ勲章オフィサー - 研究分野：計算複雑性
読者の質問
### P versus NP問題とは何ですか？
効率的に検証可能な答えを持つすべての決定問題が、効率的なアルゴリズムによって解くこともできるかという問いです。
### クック・レヴィンの定理とは何ですか？
ブール満充足可能性問題がNP完全であるという形式的な証明であり、スティーブン・クック（Stephen Cook）とレオニード・レヴィン（Leonid Levin）によって独立に確立されました。
