スティーブン・クック（Stephen A. Cook, 1939年12月14日 - ）は、米国・カナダの計算機科学者・数学者。専門は計算理論、特に計算複雑性理論の論理学的側面や(証明複雑性)の研究に従事している。2012年現在、トロント大学計算機科学科と数学科の教授である。
| スティーブン・アーサー・クック | |
|---|---|
| 2008年 | |
| 生誕 | 1939年12月14日（83歳） ニューヨーク州バッファロー |
| 研究分野 | 計算機科学 |
| 研究機関 | カリフォルニア大学バークレー校 トロント大学 |
| 出身校 | ハーバード大学 ミシガン大学 |
| 博士課程 指導教員 | ハオ・ワン |
| 博士課程 指導学生 | ウォルター・サヴィッチ |
| 主な業績 | NP完全性 命題論理(証明複雑性) (クック-レビンの定理) |
| 主な受賞歴 | チューリング賞(1982) |
| プロジェクト:人物伝 | |
経歴
ニューヨーク州バッファロー生まれ。1961年ミシガン大学卒業。ハーバード大学で1962年に修士号、1966年に博士号取得。同年カリフォルニア大学バークレー校数学科助教授となったが、1970年には在職権を更新できなかった。バークレーの電気工学・計算機科学科の30周年式典でのスピーチで、チューリング賞受賞者で同大学教授リチャード・カープは「数学科を説得して彼に在職権を与えさせられなかったのは、我々の永遠の恥辱である」と述べた[1]。同年トロント大学計算機科学・数学科の准教授となり、1975年には教授、1985年には大学教授 (University Professor) となった（現職）。
研究
博士課程では、関数、特に乗法の複雑性を研究。1966年に博士号を取得した。数年後の1971年の論文 "The Complexity of Theorem Proving Procedures"（定理証明手続きの複雑性）[2][3]で、多項式時間変換（チューリング還元）の記法とNP完全性を定式化し、充足可能性問題 (SAT) がNP完全だと示すことでNP完全問題の存在を証明した。特に後者の件はソビエト連邦の(レオニード・レビン)も独自に発見しており、(クック-レビンの定理)と呼ばれている。その論文では計算機科学最大の問題である「P対NP問題」も定式化している。「P対NP問題」は非形式的には、答えの正しさや最適さを効率的に確認できるあらゆる最適化問題について効率的アルゴリズムで最適に解くことができるかどうか、という問題である。日常生活におけるそのような最適化問題は豊富に存在するので、「P対NP問題」への肯定的な答えが得られれば、実用的にも哲学的にも意義深い結果となる。
クックは、（容易に解を検証可能な）最適化問題の中に効率的アルゴリズムで解けないものがある、すなわち P と NP は等しくないと予想した。この予想は計算複雑性理論の研究を活発化させ、それによって計算問題の本質的複雑性への理解が深まり、効率的に計算できる問題についても理解が深まった。クックのP≠NP予想は今も証明されておらず、有名な7つのミレニアム懸賞問題の1つとされている[4][5]。
その計算複雑性理論への多大な貢献により、82年のチューリング賞を受賞。 受賞理由は次の通り。
重要かつ意義深い方法で我々の計算複雑性への理解を高めさせた貢献に対して。彼の重要な論文 The Complexity of Theorem Proving Procedures は1971年 ACM SIGACT 計算理論シンポジウムで発表され、NP完全性の理論の基礎となった。過去10年間、この領域は計算機科学の中でも最も活発な研究の場となった。
1975年に発表した論文 "Feasibly Constructive Proofs and the Propositional Calculus"[6]で、多項式時間の概念のみを使った証明の記述を定式化するPV (Polynomial-time Verifiable) 方程式理論を提唱。1979年には指導学生 Robert A. Reckhow と連名の論文 "The Relative Efficiency of Propositional Proof Systems"[7]では、p-simulation と効率的な(命題証明系)の記法を定式化し、そこから命題論理(証明複雑性)と呼ばれる分野が生まれた。彼らは「あらゆる真の論理式について短い証明がある証明系の存在」と NP = coNP が等価であることを証明した。クックはこの分野について指導学生 Phuong The Nguyen と共同で "Logical Foundations of Proof Complexity" という本を執筆している[8]。
受賞歴
- 1977年 - Steacie Fellowship
- 1982年 - Killam Research Fellowship
- 1982年 - チューリング賞
- 1999年 - CRM-Fields-PIMS prize
- 2006年 - John L. Synge Award
- 2008年 - Association for Computing Machinery (ACM) フェロー[9]
- 2010年 - ヘルツバーグメダル
王立協会とカナダ王立協会のフェローである。また、米国科学アカデミーとアメリカ芸術科学アカデミーの会員にも選ばれている。これまでに30人の学生が彼の指導で博士号を取得している。
私生活
出典
- ^ A Personal View of Computer Science at Berkeley - Richard Karp
- ^ "The Complexity of Theorem Proving Procedures", PDF file of a scanned version
- ^ "The Complexity of Theorem Proving Procedures", PDF file of a retyped version
- ^ P vs. NP 2013年10月14日, at the Wayback Machine. problem on Millennium Prize Problems page - Clay Mathematics Institute
- ^ P vs. NP problem's official description by Stephen Cook on Millennium Prize Problems
- ^ "Feasibly Constructive Proofs and the Propositional Calculus" on ACM
- ^ "The Relative Efficiency of Propositional Proof Systems" on JStore
- ^ "Logical Foundations of Proof Complexity"'s official page
- ^ Stephen Cook on ACM Fellows
関連項目
外部リンク
- Stephen A. Cook -- Home page 公式ウェブサイト（英語）
- Oral history interview with Stephen Cook at Charles Babbage Institute, University of Minnesota.
- Stephen Cook - Mathematics Genealogy Project
- Stephen Cook at DBLP