スティーブン・アーサー・クック（Stephen Arthur. Cook, 1939年12月14日 - ）は、米国・カナダの計算機科学者・数学者。専門は計算理論、特に計算複雑性理論の論理学的側面やの研究に従事している。2012年現在、トロント大学計算機科学科と数学科の教授である。

経歴 ニューヨーク州バッファロー生まれ。1961年ミシガン大学卒業。ハーバード大学で1962年に修士号、1966年に博士号取得。同年カリフォルニア大学バークレー校数学科助教授となったが、1970年には在職権を更新できなかった。バークレーの電気工学・計算機科学科の30周年式典でのスピーチで、チューリング賞受賞者で同大学教授リチャード・カープは「数学科を説得して彼に在職権を与えさせられなかったのは、我々の永遠の恥辱である」と述べたA Personal View of Computer Science at Berkeley - Richard Karp。同年トロント大学計算機科学・数学科の准教授となり、1975年には教授、1985年には大学教授 (University Professor) となった（現職）。

研究 博士課程では、関数、特に乗法の複雑性を研究。1966年に博士号を取得した。数年後の1971年の論文 "The Complexity of Theorem Proving Procedures"（定理証明手続きの複雑性）"The Complexity of Theorem Proving Procedures", PDF file of a scanned version"The Complexity of Theorem Proving Procedures", PDF file of a retyped versionで、多項式時間変換（チューリング還元）の記法とNP完全性を定式化し、充足可能性問題 (SAT) がNP完全だと示すことでNP完全問題の存在を証明した。特に後者の件はソビエト連邦のも独自に発見しており、と呼ばれている。その論文では計算機科学最大の問題である「P対NP問題」も定式化している。「P対NP問題」は非形式的には、答えの正しさや最適さを効率的に確認できるあらゆる最適化問題について効率的アルゴリズムで最適に解くことができるかどうか、という問題である。日常生活におけるそのような最適化問題は豊富に存在するので、「P対NP問題」への肯定的な答えが得られれば、実用的にも哲学的にも意義深い結果となる。

クックは、（容易に解を検証可能な）最適化問題の中に効率的アルゴリズムで解けないものがある、すなわち P と NP は等しくないと予想した。この予想は計算複雑性理論の研究を活発化させ、それによって計算問題の本質的複雑性への理解が深まり、効率的に計算できる問題についても理解が深まった。クックのP≠NP予想は今も証明されておらず、有名な7つのミレニアム懸賞問題の1つとされているP vs. NP problem on Millennium Prize Problems page - Clay Mathematics InstituteP vs. NP problem's official description by Stephen Cook on Millennium Prize Problems。

その計算複雑性理論への多大な貢献により、1982年のチューリング賞を受賞。 受賞理由は次の通り。

重要かつ意義深い方法で我々の計算複雑性への理解を高めさせた貢献に対して。彼の重要な論文 The Complexity of Theorem Proving Procedures は1971年 ACM SIGACT 計算理論シンポジウムで発表され、NP完全性の理論の基礎となった。過去10年間、この領域は計算機科学の中でも最も活発な研究の場となった。

1975年に発表した論文 "Feasibly Constructive Proofs and the Propositional Calculus""Feasibly Constructive Proofs and the Propositional Calculus" on ACMで、多項式時間の概念のみを使った証明の記述を定式化するPV (Polynomial-time Verifiable) 方程式理論を提唱。1979年には指導学生 Robert A. Reckhow と連名の論文 "The Relative Efficiency of Propositional Proof Systems""The Relative Efficiency of Propositional Proof Systems" on JStoreでは、p-simulation と効率的なの記法を定式化し、そこから命題論理と呼ばれる分野が生まれた。彼らは「あらゆる真の論理式について短い証明がある証明系の存在」と NP = coNP が等価であることを証明した。クックはこの分野について指導学生 Phuong The Nguyen と共同で "Logical Foundations of Proof Complexity" という本を執筆している"Logical Foundations of Proof Complexity"'s official page。

クックの主な研究領域は計算複雑性理論とであり、プログラム意味論、並列計算、人工知能にも関心を寄せている。

受賞歴 1977年 - Steacie Fellowship 1982年 - Killam Research Fellowship 1982年 - チューリング賞 1999年 - CRM-Fields-PIMS prize 2006年 - John L. Synge Award 2008年 - Association for Computing Machinery (ACM) フェローStephen Cook on ACM Fellows 2010年 - ヘルツバーグメダル

王立協会とカナダ王立協会のフェローである。また、米国科学アカデミーとアメリカ芸術科学アカデミーの会員にも選ばれている。これまでに30人の学生が彼の指導で博士号を取得している。

私生活 子どもは2人おり、2012年現在は妻と共にトロント在住。趣味はヴァイオリンとセーリング。

脚注

関連項目 ハーバード大学の人物一覧

外部リンク 本人のウェブページ（英語） Oral history interview with Stephen Cook at Charles Babbage Institute, University of Minnesota.

Stephen Cook at DBLP