スティーブン＝クックの情報 （StephenArthurCook）
芸能人・有名人Wiki検索（誕生日、出身地）

スティーブン＝クックのプロフィール Wikipedia（ウィキペディア）

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

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

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

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

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

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

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

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

1977年 - Steacie Fellowship

1982年 - Killam Research Fellowship

1982年 - チューリング賞

1999年 - CRM-Fields-PIMS prize

2006年 - John L. Synge Award

2008年 - Association for Computing Machinery (ACM) フェロー

2010年 - ヘルツバーグメダル

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

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

^ 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 Archived 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

ハーバード大学の人物一覧

本人のウェブページ（英語）

Oral history interview with Stephen Cook at Charles Babbage Institute, University of Minnesota.

Stephen Cook - Mathematics Genealogy Project

Stephen Cook at DBLP

表

話

編

歴

アラン・パリス (1966)

モーリス・ウィルクス (1967)

リチャード・ハミング (1968)

マービン・ミンスキー (1969)

ジェームズ・H・ウィルキンソン (1970)

ジョン・マッカーシー (1971)

エドガー・ダイクストラ (1972)

チャールズ・バックマン (1973)

ドナルド・クヌース (1974)

アレン・ニューウェル / ハーバート・サイモン (1975)

マイケル・ラビン / デイナ・スコット (1976)

ジョン・バッカス (1977)

ロバート・フロイド (1978)

ケネス・アイバーソン (1979)

アントニー・ホーア (1980)

エドガー・F・コッド (1981)

スティーブン・クック (1982)

ケン・トンプソン / デニス・リッチー (1983)

ニクラウス・ヴィルト (1984)

リチャード・カープ (1985)

ジョン・ホップクロフト / ロバート・タージャン (1986)

ジョン・コック (1987)

アイバン・サザランド (1988)

ウィリアム・カハン (1989)

フェルナンド・J・コルバト (1990)

ロビン・ミルナー (1991)

バトラー・ランプソン (1992)

ユリス・ハルトマニス / リチャード・スターンズ (1993)

エドワード・ファイゲンバウム / ラジ・レディ (1994)

マヌエル・ブラム (1995)

アミール・プヌーリ (1996)

ダグラス・エンゲルバート (1997)

ジム・グレイ (1998)

フレデリック・ブルックス (1999)

アンドリュー・チーチー・ヤオ (2000)

オーレ＝ヨハン・ダール / クリステン・ニゴール (2001)

ロナルド・リベスト / アディ・シャミア / レオナルド・エーデルマン (2002)

アラン・ケイ (2003)

ヴィントン・サーフ / ロバート・カーン (2004)

ピーター・ナウア (2005)

フランシス・E・アレン (2006)

エドムンド・クラーク / アレン・エマーソン / ジョセフ・シファキス (2007)

バーバラ・リスコフ (2008)

チャック・サッカー (2009)

レスリー・ヴァリアント (2010)

ジューディア・パール (2011)

シャフィ・ゴールドワッサー / シルビオ・ミカリ (2012)

レスリー・ランポート (2013)

マイケル・ストーンブレーカー (2014)

マーティン・ヘルマン / ホイットフィールド・ディフィー (2015)

ティム・バーナーズ＝リー (2016)

ジョン・ヘネシー / デイビッド・パターソン (2017)

ヨシュア・ベンジオ / ジェフリー・ヒントン / ヤン・ルカン (2018)

エドウィン・キャットマル / パット・ハンラハン (2019)

アルフレッド・エイホ / ジェフリー・ウルマン (2020)

ジャック・ドンガラ (2021)

ロバート・メトカーフ (2022)

アヴィ・ヴィグダーソン (2023)

コンピュータ

カテゴリ

FAST

ISNI

VIAF

ドイツ

イスラエル

アメリカ

チェコ

オランダ

計算機協会

DBLP

Google Scholar

MathSciNet

Mathematics Genealogy Project

Scopus

zbMATH

IdRef

カナダの数学者

アメリカ合衆国の数学者

アメリカ合衆国の計算機科学者

カナダの計算機科学者

チューリング賞受賞者

王立協会フェロー

カナダ王立協会フェロー

アメリカ科学振興協会フェロー

米国科学アカデミー会員

アメリカ芸術科学アカデミー会員

ゲッティンゲン科学アカデミー会員

ACMフェロー

20世紀の数学者

21世紀の数学者

数学に関する記事

トロント大学の教員

カリフォルニア大学バークレー校の教員

ハーバード大学出身の人物

バッファロー出身の人物

1939年生

存命人物

ジョン・L・シング賞の受賞者

Webarchiveテンプレートのウェイバックリンク

FAST識別子が指定されている記事

ISNI識別子が指定されている記事

VIAF識別子が指定されている記事

GND識別子が指定されている記事

J9U識別子が指定されている記事

LCCN識別子が指定されている記事

NKC識別子が指定されている記事

NTA識別子が指定されている記事

ACM-DL識別子が指定されている記事

DBLP識別子が指定されている記事

Google Scholar識別子が指定されている記事

MATHSN識別子が指定されている記事

MGP識別子が指定されている記事

Scopus識別子が指定されている記事

ZBMATH識別子が指定されている記事

SUDOC識別子が指定されている記事