图灵奖：理查德·斯特恩斯（1993）

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

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

本文来自 wiki:Richard E. Stearns，翻译基于 谷歌翻译.

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

理查德·斯特恩斯，（Richard Edwin Stearns， 1936 年 7 月 5 日出生），美国计算机科学家。

他与 Juris Hartmanis 一起获得了 1993 年 ACM 图灵奖。

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

生平

斯特恩斯于 1958 年获得卡尔顿学院数学学士学位，获得博士学位。

1961 年，在哈罗德·W·库恩 (Harold W. Kuhn) 的指导下完成题为“无额外支付的三人合作游戏”（Three person cooperative games without side payments）的博士论文后，获得普林斯顿大学数学博士学位。

斯特恩斯现在是纽约州立大学奥尔巴尼大学计算机科学系的杰出名誉教授。

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

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

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

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

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

~~

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

至少点个赞再走吧~

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