Juris Hartmanis & Richard Stearns：他们用数学证明了"时间是有价值的"，为复杂性理论打下地基，让P vs NP成为可能

图灵奖第二十八届（1993）| Juris Hartmanis & Richard Stearns：他们用数学证明了”时间是有价值的”，为复杂性理论打下地基，让P vs NP成为可能

一句话概括：图灵告诉我们哪些问题”能算”，他们告诉我们哪些问题”难算”——1965年的一篇论文开创了计算复杂性理论，让我们第一次能用数学语言讨论算法的”快慢”。

🏆 获奖简介

Juris Hartmanis（尤里斯·哈特马尼斯，1928-2022）和Richard Edwin Stearns（理查德·埃德温·斯特恩斯，1936-）是计算复杂性理论的共同创始人，现代算法分析的奠基人。

Juris Hartmanis：

出生时间：1928年7月5日
出生地点：拉脱维亚里加
逝世时间：2022年7月29日（享年94岁）

Richard E. Stearns：

出生时间：1936年7月5日
出生地点：美国新泽西州
获奖年份：1993年（共同获奖）
获奖原因：1965年发表的开创性论文”On the Computational Complexity of Algorithms”（论算法的计算复杂性）

为什么他们是第二十八位？ 在1965年之前，计算机科学家知道某些问题”可计算”（图灵的可判定性理论），但不知道计算这些问题需要多少资源。Hartmanis和Stearns的论文改变了一切——他们首次系统地定义了TIME(f(n))和SPACE(f(n))这些复杂性类，证明了层次定理（给定更多时间确实能解决更多问题），为后来的Cook定理、Karp归约、P vs NP问题奠定了数学基础。可以说，没有他们的工作，就没有今天整个计算复杂性理论大厦。

🚀 他们的重大贡献

1. 1965年的奠基论文:开启新纪元

“On the Computational Complexity of Algorithms”

历史背景:

1930s-1950s:可计算性理论(图灵、丘奇)告诉我们哪些问题”能算”
1960s初:算法分析零散,没有统一框架
缺失环节:我们知道某些问题可计算,但不知道”有多难”

Hartmanis和Stearns的突破:

1.1 用图灵机步数衡量复杂度

核心思想:

算法的”复杂度”不是抽象概念,而是图灵机执行的步数
输入大小为n时,算法需要T(n)步完成

形式化定义: 如果存在一台图灵机M,对于大小为n的输入,M在T(n)步内停机并给出正确答案,则问题L∈TIME(T(n))。

意义: 这是第一次用数学严格定义”算法效率”。

1.2 时间复杂性类的定义

TIME(f(n)): 所有可以在时间f(n)内解决的问题集合。

例子:

TIME(n):线性时间可解问题
TIME(n²):平方时间可解问题
TIME(2^n):指数时间可解问题

关键性质:

如果f(n) < g(n),则TIME(f(n)) ⊆ TIME(g(n))
但这个包含是”非严格”的吗?即是否TIME(f(n)) ≠ TIME(g(n))?

1.3 时间层次定理(Time Hierarchy Theorem)

Hartmanis-Stearns的核心结果:

定理: 如果f(n)和g(n)都是”时间可构造”的,并且g(n) = o(f(n)/log f(n)),那么:

TIME(g(n)) ⊊ TIME(f(n))

(⊊表示”真包含”,即右边严格大于左边)

通俗理解:

给定显著更多的时间,我们确实能解决更多问题
不是所有问题都能用”聪明算法”在更短时间内解决
时间是真实的限制,不可魔法般消除

例子:

TIME(n) ⊊ TIME(n²):平方时间严格强于线性时间
TIME(n²) ⊊ TIME(n³):立方时间严格强于平方时间
TIME(2^n) ⊊ TIME(2^(2n)):双指数严格强于单指数

证明思路(对角化):

枚举所有在g(n)时间内运行的图灵机:M1, M2, M3, …
构造一个新问题L:对于输入x,模拟M_i(x)(其中i是x的编号),用相反的答案
L可在f(n)时间内解决(因为f(n)足够大,可以模拟g(n))
但L不在TIME(g(n))中(因为对于任何g(n)时间的机器Mi,L在输入i上给出相反的答案)

哲学意义: 这证明了”时间是有价值的”,不能总是用聪明算法弥补。

2. 空间复杂性理论

SPACE(f(n)): 使用至多f(n)个存储单元可解决的问题集合。

关键区别:

时间:用过的时间不能重用
空间:内存可以覆盖重用

空间层次定理: 类似时间层次定理,但条件稍有不同:

如果g(n) = o(f(n)),则SPACE(g(n)) ⊊ SPACE(f(n))

2.1 Savitch定理

Hartmanis参与证明:

NSPACE(f(n)) ⊆ DSPACE(f(n)²)

(非确定性空间可以用确定性的平方空间模拟)

应用:

PSPACE = NPSPACE(不确定性在空间上不增加能力!)
这与时间复杂性形成对比(P vs NP未知)

3. 复杂性类的结构

P(Polynomial Time): P = ∪_k TIME(n^k)

PSPACE: PSPACE = ∪_k SPACE(n^k)

关系: P ⊆ NP ⊆ PSPACE ⊆ EXPTIME

Hartmanis和Stearns为这些定义提供了基础。

4. 可计算性与复杂性的桥梁

之前:

图灵:某些问题不可计算(停机问题)

Hartmanis-Stearns之后:

在可计算问题中,有些”容易”(多项式时间)
有些”困难”(指数时间甚至更高)
有严格的数学证明

层次:

不可计算 (停机问题)
  ↓
可计算但不一定高效 (递归可枚举)
  ↓  
高效可计算 (P)
  ↓
超高效 (对数空间、常数时间等)

🌍 对世界的深远影响

1. 为NP完全性理论铺路

时间线:

1965: Hartmanis-Stearns定义复杂性类
1971: Stephen Cook证明SAT是NP完全
1972: Richard Karp证明21个问题NP完全
1985: Karp因此获图灵奖

没有Hartmanis-Stearns的框架,就没有Cook-Levin定理,也没有后续的NP完全性理论。

2. 密码学的理论基础

现代密码学依赖”计算困难性”:

RSA:大整数分解困难(非多项式时间?)
DH:离散对数困难
AES:对称密码的密钥空间足够大(暴力破解需指数时间)

Hartmanis-Stearns教会我们如何严格定义和证明”困难”。

3. 算法分析的标准

今天每个计算机科学课程都讲:

时间复杂度:O(n log n)、O(n²)
空间复杂度:O(n)、O(1)

所有这些都建立在Hartmanis-Stearns的形式化框架之上。

4. 实际系统设计的指导

工程师学会:

某些问题本质上困难(如NP完全),不要浪费时间找”完美算法”
转向近似算法、启发式、参数化
理解资源限制:时间 vs 空间的权衡

🏆 获奖理由(通俗版)

ACM官方表彰:“表彰他们在建立计算复杂性理论基础方面的论文《论算法的计算复杂性》。”

更通俗的理解: Hartmanis和Stearns用数学语言回答了最基本的问题:“这个算法有多快?""能不能更快?""给定更多时间/空间,能解决更多问题吗?”

他们不是发明了一个聪明的算法,而是创造了一个思考和讨论算法效率的整个框架。这个框架影响了此后50年的所有计算机科学研究。

他们证明了:

定量分析是可能的:算法效率可以严格证明
资源是有价值的:时间和空间不能魔法般消失
存在本质困难的问题:不是所有问题都有高效解法

👤 个人生平与传奇

Juris Hartmanis(1928-2022)

早年传奇:

1928年:出生于拉脱维亚里加
二战:家庭逃离苏联,辗转德国难民营
1949年:移民美国,几乎身无分文
1951年:堪萨斯城市大学物理学士(边打工边上学)
1955年:加州理工学院数学博士

学术生涯:

1958年:加入通用电气研究实验室
1965年:与Stearns合作发表开创性论文
1965年:转到康奈尔大学
建立康奈尔理论CS系:成为世界顶尖理论计算机科学中心

性格:

严谨的数学家:每个定理都要严格证明
谦逊:总说”我们只是问了正确的问题”
导师:培养了众多理论计算机科学家

晚年:

1992-1993: NSF计算机与信息科学与工程部门主管
1995年:康奈尔大学荣休教授
2022年:逝世,享年93岁

Richard Stearns(1936-)

背景:

1936年:出生于美国新泽西州
1958年:卡尔顿学院数学学士
1961年:普林斯顿大学数学博士

学术与工业生涯:

1961-1985年:通用电气研究实验室
- 与Hartmanis合作的黄金时期
- 研究自动机理论、形式语言、复杂性
1985年:转到纽约州立大学奥尔巴尼分校
至今:荣休教授,仍活跃

性格:

合作精神强:与Hartmanis形成完美拍档
跨界思维:从数学到计算机科学
低调:相比Hartmanis,更少公开演讲,专注研究

传奇的合作

相识: 1958年都在通用电气研究实验室

互补:

Hartmanis:抽象思维、数学严谨
Stearns:构造性证明、具体例子

合作模式:

长时间讨论:在黑板前一站几小时
互相挑战:一个提想法,另一个找漏洞
共同完善:反复推敲每个定义和定理

1965年的突破: 几个月的密集合作,终于形式化了复杂性度量,证明了层次定理。

💭 为什么他们值得纪念?

1. 他们是”测量员”,不是”建造者”

大多数图灵奖得主:

发明了算法(快速排序、RSA)
创造了系统(Unix、Alto)
设计了语言(Lisp、Simula)

Hartmanis和Stearns:

没有发明具体算法
但创造了衡量所有算法的标尺

类比: 他们不是建筑师,而是发明了”米尺”和”千克”的人——定义了度量标准本身。

2. 他们的工作是”元理论”

复杂性理论是关于”理论的理论”:

不研究具体问题,而是研究”问题的难度”这一概念本身
不设计算法,而是证明”某些问题必然需要这么多资源”

这种抽象层次的工作极其困难,但影响最深远。

3. 他们定义了”可能”与”不可行”的边界

图灵:划分”可计算”与”不可计算”
Hartmanis-Stearns:划分”高效可计算”与”理论可计算但不实际”

实际意义:

工程师知道哪些问题值得努力
研究者知道哪些方向值得探索
密码学家知道什么假设可以依赖

4. 他们的遗产每天都在被使用

每次你说:

“这个算法是O(n log n)”
“这个问题是NP完全的”
“我们需要权衡时间和空间”

你都在使用Hartmanis-Stearns创造的语言和框架。

🔍 技术深度:层次定理的证明思路

对角化技术

灵感来源: 康托尔证明实数不可数

应用到复杂性:

枚举:列出所有在时间g(n)内运行的图灵机
构造对角问题:L = {x | M编号(x)不接受x}
时间分析:
- 判定L需要模拟M编号(x),需要g(|x|)时间
- 加上编码开销,总时间≈ g(n) · log g(n)
- 如果f(n)显著大于g(n) log g(n),我们有足够时间解决L
矛盾:L在TIME(f(n))中,但不在TIME(g(n))中

时间可构造函数

定义: 函数f(n)是时间可构造的,如果存在图灵机在O(f(n))时间内,输入1^n,输出f(n)的二进制表示。

意义:

排除病态函数(如不可计算的函数)
n, n log n, n², 2^n都是时间可构造的

🧪 实践意义:复杂性思维的应用

对算法设计者

问题分类:

P:可以高效解决 → 寻找多项式算法
NP完全:很可能困难 → 考虑近似/启发式
PSPACE完全:更困难 → 限制问题规模或改变问题

资源权衡:

时间-空间权衡:哈希表(空间换时间)
预处理-查询权衡:倒排索引

对密码学家

安全性依赖:

单向函数:正向计算容易,反向计算难
陷门函数:有”后门”时反向容易

复杂性假设:

P ≠ NP:大部分现代密码依赖此假设
整数分解∉P:RSA的安全性

对系统设计者

性能目标:

O(1):哈希表查找
O(log n):二分搜索
O(n):线性扫描
O(n²):小心!可能成为瓶颈

避免陷阱:

嵌套循环 → O(n²)或更差
记住:常数因子很重要,但渐近复杂度更重要

📚 延伸阅读与学习路径

经典教材

入门:

Sipser: “Introduction to the Theory of Computation”
- 第7-9章详细讲解复杂性理论
- 清晰易懂,适合初学者

进阶:

Arora & Barak: “Computational Complexity: A Modern Approach”
- 现代复杂性理论的全面教材
- 包含最新发展(PCP、去随机化等)

经典:

Garey & Johnson: “Computers and Intractability”
- NP完全性的”圣经”
- 虽然关注应用,但基础是Hartmanis-Stearns的框架

原始论文

Hartmanis & Stearns (1965): “On the Computational Complexity of Algorithms”

虽然技术细节复杂,但引言和结论值得一读
感受理论计算机科学早期的思考方式

在线资源

复杂性动物园(Complexity Zoo):

列出500+复杂性类及其关系
https://complexityzoo.net

🌟 精神遗产:Hartmanis-Stearns的三大哲学

1. “严谨的定义先于深刻的定理”

教训: 在证明定理之前,必须精确定义概念。TIME(f(n))、SPACE(f(n))的形式化定义是成功的基础。

应用:

软件工程:先定义需求,再写代码
研究:先明确问题,再寻找答案

2. “量化思维胜过定性直觉”

教训: “这个算法快”不够,要知道”快多少”(O(n) vs O(n²))。

应用:

性能优化:测量,不要猜
决策:数据驱动,不是拍脑袋

3. “困难是可证明的,不仅是经验的”

教训: 某些问题的困难不是因为我们不够聪明,而是数学上的本质限制。

应用:

接受现实:有些事确实做不到
调整策略:寻找可行的替代方案

总结语: Juris Hartmanis和Richard Stearns是计算机科学的”度量学之父”。他们用严谨的数学定义了”算法有多快”这一看似简单实则深刻的问题,创造了一个思考、讨论和证明算法效率的整个框架。

从你第一次学习”时间复杂度”的概念,到密码学家设计加密算法,到工程师优化数据库查询,无处不在Hartmanis-Stearns思想的影子。他们证明了:有些问题本质困难,不能用聪明算法魔法般解决;但通过严谨分析,我们能精确理解困难的边界,从而做出明智的工程决策。

这束始于1965年的复杂性理论之光,照亮了计算的可能与极限,让我们在探索算法的道路上不再盲目,而是有了清晰的路标和可靠的指南针。

最后更新: 2024年12月 本文为图灵奖系列文章,旨在以通俗方式介绍计算机科学先驱的贡献