スティーブン・クックとは？
すてぃーぶんくっく
スティーブン・クックはカナダ系アメリカ人の計算機科学者で、NP完全問題の概念を確立し、計算複雑性理論の基礎を築いた業績でチューリング賞を受賞しました。
スティーブン・クック（Stephen Cook、1939年生まれ）は、アメリカ生まれのカナダの計算機科学者で、トロント大学の名誉教授です。計算複雑性理論の分野における最も重要な業績の一つとして知られる「クック・レヴィン定理（Cook-Levin theorem）」を1971年に発表しました。
クック・レヴィン定理は、「充足可能性問題（SAT）がNP完全である」ことを証明したものです。これにより、多項式時間で解を検証できる問題の集合（NP）の中に、最も難しい問題の集合（NP完全）が存在することが明らかになりました。
この発見は計算機科学における最大の未解決問題「P対NP問題」の定式化に直結します。P＝NPならば、現在のコンピュータでは現実的な時間内に解けない多くの問題（暗号解読・スケジューリング・経路最適化など）が効率よく解けることになるため、理論的のみならず実用上も極めて重要な問題です。
クックは1982年にACMチューリング賞を受賞しており、これは計算機科学分野における最高の栄誉とされます。
使い方・例文
スティーブン・クックが定式化したNP完全の概念は、情報工学の授業や暗号理論の研究で「P対NP問題」を説明する際に必ず登場します。
この用語をシェア
最終更新: