Loading article…
スティーブン・アーサー・クック（1939年12月14日生まれ）は、計算複雑性理論と証明複雑性の分野に多大な貢献をしたアメリカ系カナダ人のコンピュータ科学者および数学者である。トロント大学コンピュータ科学科および数学科の名誉教授である。
クックは計算複雑性理論の先駆者の一人とみなされている。彼は1982年にACMチューリング賞を受賞した。
クックは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年間、コンピュータ科学において最も活発かつ重要な研究活動の一つとなっている。
1975 年に発表された彼の論文「実行可能な構成的証明と命題論理」[ 7 ]では、多項式時間概念のみを使用して証明の概念を形式化するために、等式理論 PV (多項式時間検証可能の略) を導入しました。彼は、1979 年に学生のRobert A. Reckhowと共同で発表した論文「命題証明システムの相対的効率」[ 8 ]でこの分野にさらに大きな貢献をしました。この論文では、 p シミュレーションと効率的な命題証明システムの概念を形式化し、これが現在命題証明複雑性と呼ばれる分野の始まりとなりました。彼らは、すべての真の式が短い証明を持つ証明システムの存在はNP = coNPと同等であることを証明しました。Cook はこの分野で学生のPhuong The Nguyenと共著で「証明複雑性の論理的基礎」 [ 9 ]という本を執筆しました。
彼の主な研究分野は計算複雑性理論と証明複雑性であり、プログラミング言語の意味論、並列計算、人工知能にも手を広げている。その他、彼が貢献してきた分野には、限定算術、限定逆算術、高階型関数の複雑性、解析の複雑性、命題論理証明システムの下限などがある。
彼は複雑性クラスNCをニック・ピペンジャーにちなんで名付けた。複雑性クラスSCは彼にちなんで名付けられている。[ 10 ]複雑性クラスAC0の定義とその階層ACも彼によって導入された。[ 11 ]
ドン・クヌースによれば、KMPアルゴリズムは、線形時間で連結された回文を認識するためのクックのオートマトンに触発されたものである。[ 12 ]
クックは1977年にNSERC EWR Steacie記念フェローシップ、1982年にキラム研究フェローシップを受賞し、1999年にはCRM-Fields-PIMS賞を受賞しました。彼はジョン・L・シンジ賞とチェコ科学アカデミーのバーナード・ボルツァーノ・メダル（2008年）を受賞しており[ 13 ] 、ロンドン王立協会とカナダ王立協会のフェローでもあります。クックは米国科学アカデミーとアメリカ芸術科学アカデミーの会員に選出されています。彼はゲッティンゲン科学アカデミーの通信会員です。
クックは1982年に ACMチューリング賞を受賞しました。計算機学会は、計算複雑性理論への彼の根本的な貢献を称え、2008年に 彼をACMフェローに選出しました。[ 14 ]彼は1999年に記号論理学会によってゲーデル講演者に 選ばれました。[ 15 ]
オンタリオ州政府は2013年に彼をオンタリオ勲章に任命した。これはオンタリオ州で最高の栄誉である。 [ 16 ]彼は2012年にゲルハルト・ヘルツベルク・カナダ金メダル（科学・工学部門）を受賞した。これはカナダの科学者と技術者にとって最高の栄誉である。[ 17 ]ヘルツベルク・メダルは、NSERCによって「カナダで行われた自然科学または工学の研究活動の持続的な卓越性と全体的な影響力」に対して授与される。[ 18 ]彼は2015年にカナダ勲章オフィサーに任命された。[ 19 ] [ 20 ]
審査員の表彰状には、「コンピュータが効率的に解決できる問題とできない問題を特定する上で果たした重要な役割」が評価され、クック氏はBBVA財団フロンティア・オブ・ナレッジ賞2015の情報通信技術分野を受賞した。さらに、「複雑な計算が不可欠なあらゆる分野に劇的な影響を与えた」と評されている。
クックは数多くの修士課程学生を指導しており、36名の博士課程学生が彼の指導の下で学位を取得している。[ 1 ]
クックは妻と共にトロントに住んでいる。彼らには2人の息子がおり、そのうちの1人はオリンピックセーラーのゴードン・クックである。[ 21 ]