图灵奖：尤里斯·哈特马尼斯（1993）

图灵奖是计算机界最负盛名的奖项，有“计算机界诺贝尔奖”之称。”图灵奖”系列将介绍历届获奖者。每周二更新，本文为第 32 期。图灵奖：尤里斯·哈特马尼斯（1993）

文章来自微信公众号“科文路”，欢迎关注、互动。转发须注明出处。

本文来自 wiki:Juris_Hartmanis，翻译基于 谷歌翻译.

计算复杂性理论（Computational complexity theory）

尤里斯·哈特马尼斯，（Juris Hartmanis，1928 年 7 月 5 日~ 2022 年 7 月 29 日），是一位出生于拉脱维亚的美国计算机科学家和计算理论家。

他与 Richard E. Stearns 一起获得了 1993 年 ACM 图灵奖。

其图灵奖颁奖词为“与理查德·E·斯特恩斯 (Richard E. Stearns) 合作，表彰他们为计算复杂性理论领域奠定基础的开创性论文”。（*With Richard E. Stearns, in recognition of their seminal paper which established the foundations for the field of computational complexity theory.*）

生平

哈特马尼斯于 1928 年 7 月 5 日出生于拉脱维亚。他是拉脱维亚陆军将军马蒂斯·哈特马尼斯的儿子。他是诗人阿斯特丽德·伊瓦斯克的弟弟。

1940 年苏联占领拉脱维亚后，马蒂斯·哈特马尼斯被苏联逮捕并死在监狱中。 第二次世界大战后期，他的遗孀和孩子于 1944 年作为难民离开拉脱维亚。

他们首先搬到了德国，Juris Hartmanis 在那里获得了马尔堡大学物理学硕士学位的同等学位。

随后，他移居美国，于 1951 年在堪萨斯城大学（现称为密苏里大学堪萨斯城分校）获得应用数学硕士学位，并于 1955 年在 Robert P. Dilworth 的指导下获得加州理工学院数学博士学位。

随后，在康奈尔大学和俄亥俄州立大学教授数学后，Hartmanis 于 1958 年加入通用电气研究实验室。在通用电气期间，他发展了计算复杂性理论的许多原理。

1965年，他成为康奈尔大学教授。 他是该校计算机科学系（世界上最早的计算机科学系之一）的创始人之一和第一任系主任。

哈特马尼斯于 2022 年 7 月 29 日去世。

计算复杂性理论（Computational complexity theory）

计算复杂性理论（Computational complexity theory）是理论计算机科学和数学的一个分支，它致力于将可计算问题根据它们本身的复杂性分类，以及将这些类别联系起来。一个可计算问题被认为是一个原则上可以用计算机解决的问题，亦即这个问题可以用一系列机械的数学步骤解决，例如算法。

1993 年，Hartmanis 和 R.E. 斯特恩斯获得了计算机科学领域的最高奖——图灵奖。

他们的论文定义了复杂性类的基本概念，这是一种根据解决计算问题所需的时间对计算问题进行分类的方法。 他们继续证明了许多基本结果，例如时间层次定理（Time hierarchy theorem）。

理查德·M·卡普 (Richard M. Karp) 在他自己的图灵奖演讲中指出，“Juris Hartmanis 和 Richard Stearns 于 1965 年发表的论文标志着复杂性理论现代时代的开始。”

~~

都看到这儿了，不如关注每日推送的“科文路”、互动起来~

至少点个赞再走吧~

觉得还不错？可以在公众号菜单栏找到“赞赏”入口~