香农公式（「计算复杂性」理论奠基人Juris Hartmanis逝世）

机器之心报道

编辑：张倩

又一颗计算机理论巨星陨落了。

7月29日，「计算复杂性」理论奠基人、图灵奖得主Juris Hartmanis去世，享年94岁。自1965年以来，他一直是康奈尔大学计算机科学系的教授。他和计算机科学家Richard Stearns凭借1963-1965年的论文《On the Computational Complexity of Algorithms》获得了1993年的图灵奖。

Juris Hartmanis 1928年生于欧洲东北部的拉脱维亚。二战时，为躲避战火，Hartmanis一家背井离乡，Juris Hartmanis在德国的一个难民营中完成了中学学业。

之后，他进入德国马尔堡大学学习物理，并在两年半之后获得资助，前往美国堪萨斯城大学（现密苏里大学堪萨斯分校）攻读硕士学位。但由于该校没有物理学的研究生课程，Hartmanis只得改学数学。他用了一年时间取得硕士学位，并被加州理工学院接收为博士研究生，从事格论（latticetheory）的研究。

在1955年拿到博士学位后，Hartmanis曾先后在康奈尔大学和俄亥俄州立大学短暂任教。

1958年，受工业实验室的吸引，Hartmanis转入通用电气公司设在纽约州斯克内克塔迪的研究实验室，因为那里新建立了一个「信息研究部」。

Hartmanis在通用电气一待就是七年，正是在这段时间，他和Richard Stearns一起创立了计算复杂性领域。

当时，香农的信息论问世不久，香农给出了一个公式，可以计算在一定的信号和噪声平均功率之下，给定带宽的信道在单位时间内的最大信息传输量（这个公式被叫做「香农公式」)。念过物理的Hartmanis受此启发，敏锐地想到，抽象的计算过程也应该有精确的定量法则，以确定为了对每一个问题求得解答，需要多少计算工作量。

围绕这一设想，Hartmanis和曾是普林斯顿大学研究生、暑假到公司打过工、后来成为他同事的Stearns合作，开展了深入的研究，其结果就是那篇著名的论文——《On the Computational Complexity of Algorithms》。

论文链接：http://www.cs.albany.edu/~res/comp_complexity_ams_1965.pdf

这篇论文的主要贡献是将关于复杂性层次的几个不同概念和特例集合到了一个关于计算复杂性的通用理论中。他们根据任意 asymptotic bonds定义了函数和集合的时间与空间复杂性类别，证明了几个一般性的结果、线性加速以及模型在微小扰动下的稳健性。他们还讨论了逼近有理数和代数数的复杂性。尽管他们主要使用多带图灵机（计算复杂性理论中常用的一种计算模型，是简单图灵机的一种扩展）得出这些结论，但他们认为这些概念是通用的，同样的行为会出现在任何合理的模型中。

这篇论文开辟了计算机科学的一个新的研究领域，即「计算复杂性」，并奠定了它的理论基础，也让Hartmanis和Stearns最终拿到了图灵奖。

Juris Hartmanis和Richard Stearns。

1965年，Juris Hartmanis 离开通用电气公司，重返康奈尔大学，但不是回到数学系，而是负责筹建计算机科学系。由于他的眼光和魄力，也由于他的民主作风，康奈尔大学的计算机科学系吸引了一批著名学者加盟，成为美国大学中水平最高、影响最大的计算机科学系之一。

在此期间，Juris Hartmanis又在计算复杂性理论方向做了很多工作。其中，他和Leonard Berman在70年代对NP完全问题的详细结构的研究开辟了「结构复杂性理论」这一领域。他们共同提出的Berman-Hartmanis猜想（所有NP 完备语言都是多项式时间同构的）至今尚未解决。

正如美国计算机科学家Richard Lipton和Ken Regan在一篇纪念文章中所说，Hartmanis最重要的一些贡献是如此基础，包括用图灵机模拟计算复杂性(!)、通过「复杂性类」对复杂性进行研究等。知名量子计算机专家Scott Aaronson感叹说，「整个『Complexity Zoo』其实本来可以叫『Jurisic Park』的」（Complexity Zoo指的是计算领域的所有复杂度类集组成的空间）。

在悼念Juris Hartmanis的博客中，Scott Aaronson后悔自己在康奈尔大学读本科时没有深入了解Hartmanis，只是在毕业之后才有了更多接触。他感慨说，「Hartmanis是如此的体贴、善良，几乎像祖父一样，我意识到我没有在读书时就来找他是多么愚蠢。」

事实证明，Hartmanis的确对找他请教、合作的学生产生了深远影响，「粒度复杂性」领域的主要奠基人、MIT教授Ryan Williams便是其中之一。

Ryan Williams

Ryan Williams本科时因在数学理论方面成绩不佳而被导师建议不要读研，但他对「P vs NP」和「P vs PSPACE」等问题又格外痴迷。在Juris Hartmanis的课堂上，Ryan Williams得到了很大的启发和鼓舞，他对复杂性的直觉也很快得到了发展，甚至整个数学知识体系都被大大提升。

「在我生命中的那段时间，我觉得没有人相信我，奇怪的是图灵奖得主是最相信我的人。」Ryan Williams写道。

在Juris Hartmanis的鼓励和帮助下，Ryan Williams先后在SODA、IJCAI等计算机顶级会议上发表了自己的文章，并成功地被一些研究生院录取。

如今，Ryan Williams已经成为了MIT的电气工程与计算机科学教授，继续在解决「P vs. NP」问题的道路上前进。

「我非常庆幸能认识他。如果没有他的信任，我永远不会成为一名理论计算机科学家。如果没有他最初的影响，我永远不会成为一位优秀的理论计算机科学家。我在泪水中完成了这篇博客，希望每位读者都有机会对年轻人的人生产生如此深刻的影响。」Ryan Williams在博客的结尾写道。参考链接：http://www.techcn.com.cn/index.php?edition-view-132459-3https://baike.baidu.com/item/%E5%B0%A4%E9%87%8C%E6%96%AF%C2%B7%E5%93%88%E7%89%B9%E9%A9%AC%E5%B0%BC%E6%96%AF/12586960?fr=aladdinhttps://usobit.com/obituaries-2022/juris-hartmanis-july-5-1928-july-29-2022-age-94/https://scottaaronson.blog/?p=6622