1993 · 理论与算法

多少计算资源才够？

复杂性理论研究求解问题需要多少时间和内存。

尤里斯·哈特马尼斯 · 理查德·斯特恩斯

1993图灵奖

视觉指南

奖项，化为图解

阅读图解文字

基于资源的分类，为比较问题和理解计算边界提供了语言。

复杂性类别描述的是数学模型和不断增长的输入族，并不是某台机器上的一次秒表测量。

01 · 核心想法

尤里斯·哈特马尼斯和理查德·斯特恩斯奠定了计算复杂性理论的基础。他们不只问问题能否计算，还研究输入增大时需要多少资源。他们的工作帮助揭示，给予更多计算时间，确实可能增加机器能够解决的问题。

基于资源的分类，为比较问题和理解计算边界提供了语言。

02 · 人物

尤里斯·哈特马尼斯通过研究时间和内存如何限制算法，帮助创建计算复杂性理论。他与理查德·斯特恩斯在通用电气建立按计算资源分类问题的框架，并证明层次结构结果。他后来建设康奈尔大学计算机科学系。他的研究把关注点从问题是否可计算，推进到求解需要多少计算资源。

理查德·斯特恩斯在通用电气与尤里斯·哈特马尼斯共同奠定计算复杂性理论基础。他们把时间与空间明确作为分类计算问题的数学资源。斯特恩斯还研究自动机、算法和博弈论。他后来在纽约州立大学奥尔巴尼分校任教，推动计算机科学研究与教育，并担任系主任。

03 · 延伸阅读

本站原创讲解依据官方获奖记录。领域标签用于编辑导航。