クックとは？
くっく
クックは、計算複雑性理論における「NP完全」の概念を確立し、計算困難性研究の礎を築いた20世紀アメリカの計算機科学者です。
スティーブン・クック（Stephen Arthur Cook、1939年〜）は、アメリカ生まれのカナダの計算機科学者・数学者です。ハーバード大学、ミシガン大学で学び、現在はトロント大学の名誉教授です。
クックの最大の業績は、1971年の論文「定理証明可能性の複雑性（The Complexity of Theorem-Proving Procedures）」において、NP完全（NP-complete）という概念を定式化したことです。この論文で彼は、命題論理の充足可能性問題（SAT問題）がNP完全であることを証明しました（クック＝レヴィンの定理）。
NP完全とは、計算複雑性理論における重要な概念で、次のことを意味します。
- 問題の答えが「YES」の場合、その証拠を多項式時間で検証できる（NP問題）
- すべてのNP問題を多項式時間でこの問題に変換できる（NP困難）
「P≠NP予想」はミレニアム懸賞問題のひとつであり、「効率よく解ける問題と答えを確認するだけなら効率よくできる問題は同じか」という未解決の問いです。クックの定式化はこの問いの出発点となりました。
SAT問題を皮切りに、巡回セールスマン問題・グラフ彩色問題など多数の重要問題がNP完全であることが次々と示され、アルゴリズム設計や暗号理論の基礎となっています。クックは1982年にチューリング賞を受賞しています。
使い方・例文
「この最適化問題はNP完全なので、大規模インスタンスでは近似アルゴリズムや発見的手法を使う必要がある」という文脈で、アルゴリズムや計算理論の授業・研究で頻繁に登場する概念です。
この用語をシェア
最終更新: