Loading article…
スティーブン・クック | |
|---|---|
 2008年の料理 | |
| 生まれる | スティーブン・アーサー・クック 1939年12月14日 ニューヨーク州バッファロー |
| 母校 | ハーバード大学 ミシガン大学 |
| 知られている | NP完全性 命題証明の複雑性 クック・レビンの定理 |
| 受賞歴 |
|
| 科学者としてのキャリア | |
| フィールド | コンピュータサイエンス |
| 機関 | トロント大学 カリフォルニア大学バークレー校 |
| 論文 | 関数の最小計算時間について (1966) |
| 博士課程の指導教員 | 王浩 |
| 博士課程の学生 | マーク・ブレイバーマン[1] トニアン・ピタッシ ウォルター ・サヴィッチ アルヴィンド ・グプタ アンナ ・ルビウ |
スティーブン・アーサー・クック （ 1939年12月14日生まれ）は、アメリカ系カナダ人のコンピュータ科学者、数学者であり、計算量理論と証明の複雑性の分野に多大な貢献をした。トロント大学コンピュータサイエンス学部と数学部の名誉教授である。
彼は計算複雑性理論の先駆者の一人と考えられている。
バイオグラフィー
.jpg/500px-Stephen_A._Cook_1968_(enlarged_portion).jpg)
クックは1961年にミシガン大学で学士号を取得し、ハーバード大学で1962年に修士号と1966年に博士号を数学科で取得した。[2] 1966年にカリフォルニア大学バークレー校数学科に助教授として着任し、1970年に再任を拒否されるまでそこに留まった。バークレー電気工学およびコンピュータサイエンス学科の30周年を祝うスピーチで、同じくチューリング賞受賞者でバークレー教授のリチャード・カープは「数学科を説得して彼に終身在職権を与えてもらえなかったことは我々の永遠の恥である」と述べた。[3]クックは1970年にトロント大学コンピュータサイエンス学科と数学科の助教授となり、1975年に教授に昇進し、 1985年には特別教授となった。
研究
博士課程の間、クックは関数の複雑性、特に乗算について研究した。1971年の独創的な論文「定理証明手順の複雑性」[4]で、クックは多項式時間簡約（クック簡約とも呼ばれる）とNP完全性の概念を定式化し、ブール充足問題（通常SATとして知られる）がNP完全であることを示すことによってNP完全問題の存在を証明した。この定理はソ連のレオニード・レビンによって独立に証明されたため、クック・レビンの定理という名前が付けられた。この論文では、コンピュータサイエンスで最も有名な問題であるP対NP問題も定式化された。非公式には、「P対NP」の問題は、答えが正確/最適であるかどうかを効率的に検証できるすべての最適化問題が、効率的なアルゴリズムで最適に解けるかどうかを問うものである。日常生活にはこのような最適化問題が豊富にあることを考えると、「P 対 NP」という質問に対する肯定的な答えは、おそらく実践的かつ哲学的に大きな影響を及ぼすでしょう。
クックは、効率的なアルゴリズムでは解くことができない最適化問題（簡単にチェックできる解を持つ）が存在すると予想している。つまり、PはNPと等しくない。この予想は計算複雑性理論の分野で多くの研究を生み出し、計算問題に内在する難しさと、何を効率的に計算できるかについての理解を大きく向上させた。しかし、この予想は未解決のままであり、有名な7つのミレニアム懸賞問題の1つである。[5] [6]
1982 年、クックは複雑性理論への貢献によりチューリング賞を受賞しました。受賞理由は次のとおりです。
計算の複雑さに関する理解を、意義深く深遠な方法で前進させたことに対して。1971 年の ACM SIGACT 計算理論シンポジウムで発表された彼の独創的な論文「定理証明手順の複雑さ」は、NP 完全性理論の基礎を築きました。その後の NP 完全クラスの問題の境界と性質の探究は、過去 10 年間のコンピュータ サイエンスにおける最も活発で重要な研究活動の 1 つとなっています。
1975年に発表された論文「実行可能構成的証明と命題計算」[7]で、彼は等式理論PV（Polynomial-time Verifiableの略）を導入し、多項式時間の概念のみを使用して証明の概念を形式化した。1979年に学生のロバート・A・レックハウと共同で発表した論文「命題証明システムの相対的効率」[8]でもこの分野に大きく貢献した。この論文で彼らはpシミュレーションと効率的な命題証明システムの概念を形式化し、現在では命題証明複雑性と呼ばれる分野を開始した。彼らは、すべての真の式に短い証明がある証明システムの存在は、NP = coNPと同等であることを証明した。クックは、この分野で学生のフオン・テ・グエンと共著で「証明複雑性の論理的基礎」という本を執筆した。[9]
彼の主な研究分野は、計算量理論と証明の複雑性であり、プログラミング言語の意味論、並列計算、人工知能にも及びます。彼が貢献した他の分野には、有界算術、有界逆数学、高次関数の計算量、解析の計算量、命題証明システムの下限などがあります。
その他の貢献
彼はニック・ピッペンジャーにちなんで複雑性クラスNCと名付けた。複雑性クラスSCも彼にちなんで名付けられた。[10]複雑性クラスAC 0の定義とその階層ACも彼によって導入された。[11]
ドン・クヌースによれば、KMPアルゴリズムは連結された回文を線形時間で認識するクックのオートマトンに触発されたものである。[12]
受賞と栄誉
クックは1977年にNSERC EWR Steacie Memorial Fellowship、1982年にKillam Research Fellowshipを受賞し、1999年にはCRM-Fields-PIMS賞を受賞しました。彼はチェコ科学アカデミーのジョン・L・シング賞とバーナード・ボルツァーノメダル（2008年）を受賞しており、[13]ロンドン王立協会とカナダ王立協会のフェローでもあります。クックは米国科学アカデミーとアメリカ芸術科学アカデミーの会員に選出されています。彼はゲッティンゲン科学人文アカデミーの通信会員です。
クックは1982年に ACMチューリング賞を受賞した。計算機協会は2008年に 計算複雑性理論への基礎的貢献により彼をACMフェローに選出した。[14]彼は1999年に記号論理協会からゲーデル講演を行うために 選ばれた。[15]
オンタリオ州政府は2013年に彼にオンタリオ州最高の栄誉であるオンタリオ勲章を授与した。[16]彼は2012年にカナダの科学者と技術者にとって最高の栄誉であるゲルハルト・ヘルツバーグ科学技術金メダルを受賞した。 [17]ヘルツバーグメダルは「カナダで自然科学または工学分野で行われた研究の持続的な卓越性と全体的な影響の両方」に対してNSERCから授与される。 [18]彼は2015年にカナダ勲章オフィサーに任命された。[19]
審査員の表彰文によると、クック氏は「コンピューターが効率的に解決できることとできないことを特定する上で重要な役割を果たした」として、情報通信技術部門でBBVA 財団フロンティア オブ ナレッジ アワード2015 を受賞した。さらに、同氏の業績は「複雑な計算が重要なすべての分野に大きな影響を与えた」と続けている。
クック氏は数多くの修士課程の学生を指導しており、36人の博士課程の学生が彼の指導の下で学位を取得しました。[1]
私生活
クックは妻とトロントに住んでいる。二人には2人の息子がおり、そのうちの一人はオリンピックのセーリング選手ゴードン・クックである。[20]
参照
参考文献
- ^ ab 数学系譜プロジェクトのスティーブン・クック
- ^ カプロン、ブルース。「スティーブン・アーサー・クック」。AMチューリング賞。 2018年10月23日閲覧。
- ^ Richard Karp (2003). 「バークレーにおけるコンピュータサイエンスの個人的な見解」カリフォルニア大学バークレー校。 2023年2月12日閲覧。
- ^ スティーブン・クック (1971)、定理証明手順の複雑さ(PDF) – トロント大学経由Stephen A. Cook (2009) [1971]. 「定理証明手順の複雑さ」 。 2023年2月12日閲覧。
- ^ P vs. NP アーカイブ済み 2013年10月14日、Wayback Machineミレニアム懸賞問題ページの問題–クレイ数学研究所
- ^ P vs. NP 2007年9月27日アーカイブ、Wayback Machine問題の公式説明はスティーブン・クックによるミレニアム懸賞問題で
- ^ Cook, Stephen A. (1975 年 5 月 5 日)。「実現可能な構成的証明と命題計算 (暫定版)」。第 7 回 ACM 計算理論シンポジウム議事録 - STOC '75。ニューヨーク: Association for Computing Machinery。pp. 83–97。doi : 10.1145 / 800116.803756。ISBN 978-1-4503-7419-4. S2CID 13309619。
- ^ Cook, Stephen A.; Reckhow, Robert A. (1979). 「命題証明システムの相対的効率」. The Journal of Symbolic Logic . 44 (1): 36–50. doi :10.2307/2273702. ISSN 0022-4812. JSTOR 2273702. S2CID 2187041.
- ^ 「証明の複雑さの論理的基礎」の公式ページ
- ^ 「「スティーブのクラス」：SC の起源」。理論計算機科学 – Stack Exchange。
- ^ 「複雑性クラス AC を導入したのは誰か?」理論計算機科学 – Stack Exchange。
- ^ 「ドナルド・クヌースへの20の質問」。
- ^ 「数学科学における功績によりベルナルド・ボルツァーノ名誉メダルを受賞」。CASメダル。チェコ科学アカデミー。 2024年4月13日閲覧。
- ^ Association for Computing Machinery. 「Stephen A Cook」. awards.acm.org . 2023年2月12日閲覧。
- ^ 「ゲーデル講師 - 記号論理学協会」。2021年11月8日閲覧。
- ^ 「25名の任命者がオンタリオ州最高栄誉に任命される」市民権・移民省。
- ^ Emily, Chung (2013年2月27日). 「コンピューター科学者がカナダのトップ科学賞を受賞」. cbc.ca . 2013年2月27日閲覧。
- ^ 「現在の受賞者 – 2012 – スティーブン・クック」。2016年6月28日。
- ^ “SaltWire | Halifax”. www.saltwire.com . 2023年2月12日閲覧。
- ^ 「Stephen A. Cook – ホームページ」。
外部リンク
ウィキメディア・コモンズには、スティーブン・クックに関連するメディアがあります。
- スティーブン A. クックのホームページ
- 「P対NP」と計算の限界 - トロント大学でのスティーブン・クック氏による公開講演
- ミネソタ大学チャールズ・バベッジ研究所のスティーブン・クック氏への口述歴史インタビュー。クック氏は、ミシガン大学とハーバード大学での教育、カリフォルニア大学バークレー校での初期の研究、計算複雑性の問題に対する関心の高まりについて語りました。クック氏は、1970 年にトロント大学に移ったこと、そして NP 完全性に関する研究が AM チューリング賞の受賞につながったことについて語りました。
- 数学系譜プロジェクトのスティーブン・アーサー・クック
- DBLP書誌サーバーの Stephen A. Cook