Loading article…
ユリス・ハートマニス | |
|---|---|
.jpg/500px-Juris_Hartmanis(2002).jpg) | |
| 生まれる | 1928年7月5日 リガ、ラトビア |
| 死亡 | 2022年7月29日（享年94歳） |
| 母校 | |
| 受賞歴 | チューリング賞(1993) |
| 科学者としてのキャリア | |
| フィールド | コンピュータサイエンス |
| 機関 | |
| 博士課程の指導教員 | ロバート・P・ディルワース |
| 博士課程の学生 | アラン・ボロディン(1969) デクスター・コーゼン(1977) ニール・インマーマン(1980) ジンイー・カイ(1986) [1] |
ユリス・ハートマニス（1928年7月5日 - 2022年7月29日）は、ラトビア生まれのアメリカのコンピュータ科学者、計算理論家であり、リチャード・E・スターンズとともに「計算複雑性理論の分野の基礎を確立した独創的な論文」が評価され、1993年のACMチューリング賞を受賞した。
人生とキャリア
ハルトマニスは1928年7月5日にラトビアで生まれた。[2]彼はラトビア軍の将軍であるマルティンシュ・ハルトマニス [ 3]とイルマ・マリア・ハルトマネの息子であり、詩人のアストリッド・イヴァスクの弟であった。 1940年にソ連がラトビアを占領した後、マルティンシュ・ハルトマニスはソ連に逮捕され、獄死した。第二次世界大戦後、マルティンシュ・ハルトマニスの妻と子供たちは、ソ連が再びラトビアを占領した場合の安全を恐れ、1944年に難民としてラトビアを離れた。[6] [7]
彼らはまずドイツに移り、そこでユリス・ハートマニスはマールブルク大学で物理学の修士号に相当する学位を取得した。その後アメリカに渡り、1951年にカンザスシティ大学（現ミズーリ大学カンザスシティ校）で応用数学の修士号を取得し、1955年にはロバート・P・ディルワース指導の下、カリフォルニア工科大学で数学の博士号を取得した。[8]ミズーリ大学カンザスシティ校は1999年5月に彼に名誉人文学博士号を授与した。[9]コーネル大学とオハイオ州立大学 で数学を教えた後、ハートマニスは1958年にゼネラル・エレクトリック研究所に加わった。ゼネラル・エレクトリック在籍中に、彼は計算複雑性理論の多くの原理を開発した。[15] 1965年にコーネル大学の教授となった。彼は同大学のコンピューターサイエンス学部の創設者の一人であり、初代学部長であった（同学部は世界でも最初のコンピューターサイエンス学部の一つであった）。[16]
ハートマニスは、コンピュータサイエンスとエンジニアリング（CS&E）を発展させるための国家的な取り組みにさまざまな形で貢献しました。最も重要なのは、彼が国立研究会議の研究を議長として率いたことです。この研究は、1992年に「未来のコンピューティング - コンピュータサイエンスとエンジニアリングのための幅広い課題」[17]として出版され、CS&Eの中核的な取り組みを維持し、分野を広げ、CS&Eの学部教育を改善するという優先事項に基づいた勧告を出しました。彼は、1996年から1998年まで、 国立科学財団（NSF）のコンピュータおよび情報科学およびエンジニアリング局（CISE）[18]の副局長を務めました。
1989年、ハートマニスは計算複雑性理論とコンピューティングの研究および教育への基礎的貢献により、米国工学アカデミーの会員に選出された。彼は計算機協会およびアメリカ数学会のフェローであり、[19]米国科学アカデミーの会員でもあった。[20]彼はラトビア科学アカデミーの外国人会員でもあり、[21]同アカデミーは彼のコンピュータサイエンスへの貢献により2001年に彼にグランドメダル授与した。[22]
ハートマニスは 2022 年 7 月 29 日に亡くなった[23] [24] [25]
計算複雑性：基礎的貢献
1993年、ハートマニスとR.E.スターンズはコンピュータサイエンスの最高賞であるチューリング賞を受賞した。受賞理由には「計算複雑性理論の分野の基礎を確立した独創的な論文に対して」とある。[26] 彼らの論文[13]は、計算問題を解くのに要する時間に応じて分類する方法である複雑性クラス という基本概念を定義した。彼らはその後、時間階層定理など、いくつかの基本的な結果を証明した 。リチャード・M・カープは自身のチューリング賞講演で「複雑性理論の現代時代の始まりを示すのは、1965年のジュリス・ハートマニスとリチャード・スターンズの論文である」と述べている。[27]
PM Lewis IIとともに、ハートマニスとスターンズも空間利用に基づいて計算量クラスを定義した。彼らは最初の空間階層定理を証明した。[12]同年、彼らはまた、すべての文脈自由言語が決定論的な空間計算量（log n）2を持つことを証明した[28] 。これは、空間計算量に関するサビッチの定理につながる基本的なアイデアを含んでいた。
ハートマニスはその後も数十年にわたり計算複雑性の分野に多大な貢献を続けた。レナード・バーマンとともに、すべての自然NP完全言語は多項式時間同型であることを証明し[29]、これがすべてのNP完全集合に当てはまると予想した[30] 。この予想自体は未解決のままであるが、NP完全集合の構造に関する膨大な研究につながり、最終的には疎なNP完全集合が存在しないというマハニーの定理に至った。[31] [32] [33] [34]彼と共著者らはブール階層も定義した。[35] [36]
ハートマニスの1981年の論文[14]は、この分野とオートマトン理論の発展についての個人的な説明を提供し、彼の研究を導いた根本的な信念と哲学について議論しています。彼の60歳の誕生日を記念して書かれた本[37]、特にスターンズの章[38]は、計算複雑性に関する貴重なリソースです。
1980年代後半、ハートマニスによる1956年3月20日付けのゲーデルからフォン・ノイマンへの新しく発見された手紙に関する解説[39]は、スターンズとの画期的な論文以前の計算複雑性の初期の歴史に新たな洞察をもたらし、チューリング、ゲーデル、 チャーチ、ポスト、クリーネの相互作用に触れていた。この手紙の中でゲーデルは、NP完全問題と同等の問題が2次時間または線形時間で解けるかどうかを初めて疑問視し、P = NP？問題を予見した。
受賞歴
- アメリカ科学振興協会（AAAS）フェロー、[40] 1981
- 米国工学アカデミー会員、[41] 1989
- 会員（外国人）：ラトビア科学アカデミー、[21] 1990
- アメリカ芸術科学アカデミー会員、[42] 1992
- ACMチューリング賞[26] 1993
- フンボルト財団研究賞、[43] 1993年
- ACMチャーターフェロー、[44] [45] 1994
- 名誉人文学博士、[9] 1999
- コンピューティング研究協会（CRA）優秀賞、[46] 2000
- ラトビア科学アカデミー大メダル、2001年[22]
- ACM優秀サービス賞、[47] [48] 2013
- アメリカ数学会初代フェロー、[19] 2013
- 米国科学アカデミー会員、[49] 2013
主な出版物
- 書籍
- 逐次機械の代数的構造理論[50] 1966年（REスターンズと共著）
- 実行可能な計算と証明可能な複雑さの性質[51] 1978
- 計算複雑性理論（編）[52] 1989
- 未来のコンピューティング：コンピュータサイエンスとエンジニアリングのより広範な課題（編）[53] 1992（ハーバート・リンと共著）
- 選択された記事
- 「再帰的シーケンスの計算複雑性」[10] 1964年（RE Stearnsと共著）
- 「時間とメモリ要件による計算の分類」[11] 1965年（PMルイス、REスターンズと共著）
- 「メモリ制限計算の階層」[12] 1965年（PMルイス、REスターンズと共著）
- 「アルゴリズムの計算複雑性について」[13] 1965年（REスターンズと共著）
- 文脈自由言語と文脈依存言語の認識における記憶限界[28] 1965年（PMルイス、REスターンズと共著）
- 「NPとその他の完全集合の同型性と密度について」[29] 1977年（L.バーマンと共著）
- 「理論計算機科学の発展に関する考察」[14] 1981
- 「ゲーデル、フォン・ノイマン、および P =? NP 問題」[39] 1989
インタビュー
ユリス・ハートマニスはこれまでに 4 回インタビューを受けています。そのうち 2 回はビデオが公開されています。最も影響力が大きかったのはウィリアム・アスプレイによるインタビューです。
- ウィリアム・アスプレイがACMオーラルヒストリーインタビューでハートマニスにインタビュー[4] 2009
- デイヴィッド・グリースがコーネル大学のecommonsコレクションのためにハートマニスにインタビューした[54] 2010年
- レン・シュステックは、 Communications of the ACMの記事でハートマニスにインタビューしている。[55] 2015
- David Gries がACM チューリング賞受賞者としてハートマニスにインタビュー、[5] 2018
参考文献
- ^ 「Juris Hartmanis」. mathgenealogy.org .数学系譜プロジェクト. 2022年8月4日閲覧。
- ^ セルマン、アラン L.編 (1990)。複雑性理論回顧録: ジュリス・ハートマニス60歳の誕生日を記念して、1988年7月5日。ニューヨーク、ニューヨーク: シュプリンガー・ニューヨーク。doi : 10.1007 /978-1-4612-4478-3。ISBN 978-1-4612-4478-3. S2CID 31789744 . 2022年8月4日閲覧。
- ^ バルト諸語では、固有名は語彙定数ではないが、異なる文法形式を持つ。HartmanisはHartman-is と理解されなければならない。Hartman は固有名の語幹であり、接尾辞-is はラトビア語で男性文法形式を示す。同様に、例えば哲学者カントはリトアニア語では Kant as として知られている。
- ^ ab Hartmanis , Juris (2009年7月26日)。「Dr. Juris Hartmanis インタビュー」(本文)。ウィリアム・アスプレイによるインタビュー。ニューヨーク州イサカ: ACM オーラルヒストリーインタビュー。doi : 10.1145/1141880.1775727。
- ^ ab Hartmanis, Juris (2018年5月17日). 「Juris Hartmanis、1993 ACMチューリング賞受賞者」(ビデオ)。David Griesによるインタビュー。ニューヨーク州イサカ: ACM。
- ^ インタビューの項で引用したインタビューのうち2つ[4] [5]で、ハルトマニスは、父親が領地レステンを与えられたこと、ロシアがラトビアを占領し、父親を連れ去りレステンを没収したこと、ドイツが再びラトビアを占領しレステンの一部を家族に返還したこと、そしてロシアが再びラトビアを侵略する前に家族がラトビアを離れてドイツに向かったことなど、この時期について詳しく語っている。
- ^ 「アストリッド・イヴァスクへのオマージュ：文学の光」。ワールド・リテラチャー・トゥデイ。2015年4月2日。 2022年8月4日閲覧。
- ^ Hartmanis, Juris (1955). 格子の埋め込み定理 (博士論文). Cal Tech . doi :10.7907/40KS-0T27.
- ^ ab 「ミズーリ大学名誉学位」ミズーリ大学。
- ^ ab —; Stearns, RE (1964 年 11 月 11 日)。 再帰シーケンスの計算複雑性。スイッチング回路理論と論理設計に関する第 5 回シンポジウム。プリンストン、ニュージャージー: IEEE。pp. 82–90。doi :10.1109/SWCT.1964.6。
- ^ ab —; Lewis, PM; Stearns, RE (1963 年 5 月 24 日). Wayne A. Kalenich (編).計算の時間とメモリ要件による分類. Proc. IFIP Congress 65. ニューヨーク市: Spartan Books, Inc., ワシントン DC pp. 31–35. doi :10.2307/2272795. JSTOR 2272795.
- ^ abc —; Lewis, PM; Stearns, RE (1965 年 10 月 6 日)。メモリ制限計算の階層。FOCS 65: Proc. Sixth Ann. Symp スイッチング回路理論と論理設計。ニューヨーク: IEEE。pp. 179–190。doi :10.1109/FOCS.1965.11。
- ^ abc —; Stearns, RE (1965). 「アルゴリズムの計算複雑性について」.アメリカ数学会誌. 117 : 285–306. doi : 10.2307/1994208 . JSTOR 1994208. MR 0170805.
- ^ abc — (1981)、「理論計算機科学の発展に関する考察」、IEEE Annals of the History of Computing、3 (1): 42–51、doi :10.1109/MAHC.1981.10005、hdl : 1813/6244、ISSN 1058-6180
- ^ これらの初期の論文は、計算複雑性理論の多くの原理を展開した。[10] [11] [12] [13]ハートマニスの1981年の調査論文は、計算複雑性理論の研究に関する広範な情報を提供している。[14]
- ^ パデュー大学は 1962 年に最初の CS 学部を設立しました ( 「学部の歴史」)。コーネル大学は 1965 年に CS 部門を開始しました ( 「CS 部門のタイムライン」)。スタンフォード大学「コンピューターサイエンス学部タイムライン」も同様です。、カーネギーメロン大学、「コンピュータサイエンス学部の歴史」。その他いくつか。
- ^ Hartmanis, Juris; Lin, Herbert 編 (1992)。未来のコンピューティング: コンピュータサイエンスとエンジニアリングのより広範な課題。ワシントン DC: National Academies Press。p . 288。doi :10.17226/1982。ISBN 978-0-309-04740-1。
- ^ 「Juris HartmanisがNSFのCISE局長に就任」NSF 1996年9月5日2022年8月2日閲覧。
- ^ ab アメリカ数学会フェロー一覧、2013年1月19日閲覧。
- ^ 米国科学アカデミー会員および外国人会員の選出 Archived May 27, 2013, at the Wayback Machine ,米国科学アカデミー、2013年4月30日。
- ^ ab 「外国人会員」。ラトビア科学アカデミー。1990年。 2022年7月30日閲覧。
- ^ ab "Lielā medaļa" [グランドメダル]. www.lza.lv (ラトビア語)。ラトビア科学アカデミー。 2022年1月6日のオリジナルからアーカイブ。2022 年8 月 4 日に取得。
2001 ... Juris Hartmanis、par izcilu ieguldījumu datorzinātņu attīstībā。 [2001 ... ジュリス・ハルトマニス、コンピューターサイエンスの発展に対する傑出した貢献に対して。]
- ^ 新智元 [新志源] (2022年7月31日). "图灵奖得主，"计算复杂性"理论奠基人ジュリス・ハートマニス逝世，享年94岁" [チューリング賞受賞者で「計算複雑性」理論の創始者ジュリス・ハートマニス、94歳で死去].新浪finance.sina.com。 cn (簡体字中国語) 。2022 年8 月 4 日に取得。
- ^ Waldron, Patricia (2022年8月4日). 「Juris Hartmanis、初代CS学部長、94歳で死去」Cornell Chronicle . 2022年8月5日閲覧。
- ^ ガーフィンケル、シムソン;スパフォード、ユージン H. (2022 年 10 月) 「追悼：ジュリス・ハルトマニス 1928–2022」。CACM。65 (10):14-15。土井：10.1145/3559705。
- ^ ab “Turing Award” 。ACM。1993年。 2022年7月30日閲覧。
- ^ 講演の103ページを参照: Karp, Richard M. (1986年2月). 「組合せ論、複雑性、ランダム性」. Communications of the ACM . 29 (2): 98–109. doi : 10.1145/5657.5658 . ISSN 0001-0782.
- ^ ab Lewis, PM; Stearns, RE ; — (1965 年 10 月 6 日)。文脈自由言語と文脈依存言語の認識におけるメモリ境界。FOCS 65: Proc. Sixth Ann. Symp Switching Circuit Theory and Logical Design。ミシガン州アナーバー: IEEE。pp. 191–202。doi :10.1109/FOCS.1965.14。
- ^ ab Berman, L.; — (1977). 「NP およびその他の完全集合の同型性と密度について」(PDF) . SIAM Journal on Computing . 6 (2): 305–322. doi :10.1137/0206023. hdl : 1813/7101 . MR 0455536.
- ^ バーマン・ハートマニス予想
- ^ Mahaney, Stephen R. (1982年10月). 「NPのスパース完全集合：BermanとHartmanisの予想の解決」. Journal of Computer and System Sciences . 25 (2): 130–143. doi :10.1016/0022-0000(82)90002-2. hdl : 1813/6257 .
- ^ Cai, Jin-Yi; Sivakumar, D. (1999 年 4 月)、「P のスパースハードセット: Hartmanis の予想の解決」、Journal of Computer and System Sciences、58 (2): 280–296、doi : 10.1006/jcss.1998.1615
- ^ まばらな言語
- ^ マハニーの定理
- ^ Cai, Jin-Yi; Gundermann, Thomas; —; Hemachandra, Lane A.; Sewelson, Vivian; Wagner, Klaus; Wechsung, Gerd (1988 年 12 月)、「ブール階層 I: 構造特性」、SIAM Journal on Computing、17 (6): 1232–1252、doi : 10.1137/0217078
- ^ Cai, Jin-Yi; Gundermann, Thomas; —; Hemachandra, Lane A.; Sewelson, Vivian; Wagner, Klaus; Wechsung, Gerd (1989 年 2 月)、「ブール階層 II: アプリケーション」、SIAM Journal on Computing、18 (1): 95–111、doi :10.1137/0218007
- ^ セルマン、アラン L.編 (1990)。複雑性理論回顧録。シュプリンガーニューヨーク、NY。doi : 10.1007/ 978-1-4612-4478-3。ISBN 978-1-4612-8793-3. S2CID 31789744。
- ^ Stearns, RE (1990). 「Juris Hartmanis: 計算複雑性の始まり」. Selman, Alan L. (編).複雑性理論回顧録. Springer New York, NY. doi :10.1007/978-1-4612-4478-3. ISBN 978-1-4612-8793-3. S2CID 31789744。
- ^ ab Hartmanis, Juris (1989). 「ゲーデル、フォン・ノイマン、そして P =? NP 問題」.欧州理論計算機科学協会紀要. 38 : 101–107.
- ^ 「フェロー」。アメリカ科学振興協会。1981年。 2022年7月30日閲覧。
- ^ 「NAE ウェブサイト – Dr. Juris Hartmanis」。米国工学アカデミー。
- ^ “会員”.アメリカ芸術科学アカデミー. 1992年. 2022年7月30日閲覧。
- ^ “アレクサンダー・フォン・フンボルト財団、ジュリス・ハルトマニス”.アレクサンダー・フォン・フンボルト財団。 1993年。
- ^ 「ACM Fellows」ACM 1994年2022年7月30日閲覧。
- ^ “Juris Hartmanis: ACM フェロー”. 1994年。2022 年7 月 9 日に取得。
- ^ 「Distinguished Service Award」。Computing Research Association。CRA 。 2015年1月16日。 2022年7月30日閲覧。
- ^ 「ACM Distinguished Service Award」ACM 2013年2022年7月30日閲覧。
- ^ 「Juris Hartmanis: Distinguished Service Award」 2013年. 2022年7月30日閲覧。
- ^ “名誉会員”.米国科学アカデミー (NAS) . 2022年7月31日閲覧。
- ^ —; Richard E., Stearns (1966).シーケンシャルマシンの代数的構造理論。イングルウッドクリフス、ニュージャージー州: Prentice-Hall。p. 211。ISBN 0130222771。
- ^ — (1978).実行可能な計算と証明可能な複雑さの特性フィラデルフィア、ペンシルバニア州:産業応用数学協会 (SIAM) 62 ページ。ISBN 978-0-898710-27-4。
- ^ —編 (1989). 計算複雑性理論. AMS . p. 128. ISBN 978-0-8218-0131-4。
- ^ —; リン・ハーバート編 (1992)。未来のコンピューティング：コンピュータサイエンスとエンジニアリングのより広範な課題。ワシントン DC：全米アカデミー出版。p. 288。doi : 10.17226/1982。ISBN 978-0-309-04740-1。
- ^ Hartmanis, Juris (2010 年 3 月 31 日)。「Juris Hartmanis との会話」(ビデオ)。David Griesによるインタビュー。ニューヨーク州イサカ: Internet-First University Press。
- ^ レン・シュステック (2015). 「ジュリス・ハートマニス氏へのインタビュー」。CACM。58 (4): 33-37。土井：10.1145/2736346。S2CID 35051248。
外部リンク
- AM TURING AWARD の Hartmanis の略歴、短い注釈付き参考文献
- コーネル大学でのハートマニスの経歴
- 数学系譜プロジェクトのユリス・ハートマニス