理查德·斯特恩斯（Richard Stearns）

理查德·斯特恩斯（Richard E. Stearns）是美国计算机科学家与数学家,计算复杂度理论的共同创立者,1993年图灵奖得主。他与哈特马尼斯的合作开辟了衡量算法资源的严格路径。

概述

斯特恩斯1936年生于美国,数学出身,曾在通用电气研究实验室工作,后任教于纽约州立大学奥尔巴尼分校。1965年,他与哈特马尼斯共同发表关于图灵机计算复杂度的经典论文,首次给出算法时间复杂度的严格定义,这一工作使他们共享图灵奖。

核心贡献

• 时间复杂度定义:与合作者一道用图灵机步数刻画算法难度,确立了复杂度分级的基础。
• 层级定理:参与证明了时间与空间资源越多能力越强的基本结果。
• 算法分析:在语法分析、编译和确定性下推自动机方面有重要研究。
• 博弈论:晚年研究多人博弈的计算问题,拓展了复杂度理论的应用范围。

应用场景

斯特恩斯参与创立的复杂度框架是判断算法效率与问题难度的通用语言,广泛用于算法设计、程序分析、密码学以及优化问题的可解性研究。他在解析理论方面的工作也影响了编译器技术的发展。

常见问题

问:斯特恩斯和哈特马尼斯的分工是怎样的?答:两人是紧密合作者,共同完成了奠定复杂度理论的核心论文,因此一同获得图灵奖,难以将成果割裂开来。

问:为什么用图灵机来定义复杂度?答:图灵机是抽象且通用的计算模型,以它的运行步数和存储格数为度量,可以在不依赖具体硬件的前提下客观比较算法的资源消耗。