新智元报道

编辑：Aeneas 桃子

【新智元导读】「计算复杂性」理论奠基人、1993年图灵奖得主Juris Hartmanis去世，享年94岁。

又一巨星陨落。

7月29日，「计算复杂性」理论奠基人、1993年图灵奖得主Juris Hartmanis去世，享年94岁。

首创康奈尔计算机科学系

1928年，Juris Hartmanis出生在苏联拉脱维亚(Latvia)共和国，父亲是拉脱维亚军队将军Mārtiņš Hartmanis，于1940年被捕入狱去世。

二战结束时，Hartmanis带着妻子和3个孩子移民到了德国，沦为「流民」。

Hartmanis的中学学业就是在德国哈瑙(Hanau)的难民营中完成的。1949年，他取得了马尔堡大学（University of Marburg）物理学硕士学位。

两年半后，也就是1950年，Hartmanis获得资助便移居到了美国，进入堪萨斯大学（University of Kansas）攻读硕士学位。

Hartmanis介绍自己的人生经历

但由于该校没有物理学的研究生课程，他只能改学数学。仅用了一年时间，他便在1951年取得了数学硕士学位。

紧接着，他被加州理工学院（Caltech）接收为博士研究生，从事格论 (latticetheory) 的研究。1955年在美国著名数学家Robert P. Dilworth指导下，取得了数学博士学位。

1955年-1957年，Hartmanis在康奈尔大学担任数学教师，随后加入俄亥俄州立大学数学系，担任了一年的助理教授。

之后，他便加入了通用电气公司设在纽约州斯克内克塔迪 (Schenectady) 的研究实验室。

因为那里新建立了一个「信息研究部」开展有关计算机和信息学的研究，这一新的领域激发起了Hartmanis极大的兴趣和热情。

在通用电气，Hartmanis工作了7年，并发展了许多计算复杂性理论原则。

直到1965年，Hartmanis重返康奈尔大学，担任教授。

他的这次回归，不是数学系，而是领导并成立了康奈尔大学计算机科学系——世界最早的计算机科学系之一。

由于他的眼光和魄力，也由于他的民主作风，康乃尔大学的计算机科学系吸引了一批著名学者加盟，成为美国大学中水平最高、影响最大的计算机科学系之一。

这些学者中包括霍普克洛夫特(J．E．Hopcroft，1986年图灵奖得主)、格利斯(D．Giles，1995年ACM优秀计算机教育奖获得者)、霍洛维茨(E．Horowitz)、韦格纳(P．Wegner)和肖(A．Shaw)等。

Hartmanis曾三次担任计算机科学系主任(1965-71年、1977-83年和1992-93年) ，并于1980年成为沃尔特•里德(Walter R. Reed) 工程学教授。

从教多年，Hartmanis一共有21个杰出的博士研究生。

可以看到，1986年从康奈尔大学毕业的华裔数学家和计算机科学家Jin-Yi Cai（蔡进一）便是其中一位。

也正是在1965年这段时间里，Hartmanis和Richard Stearns一起创立了计算复杂性理论，凭借这一成就摘取了1993年的图灵奖。

1996-1998年，他离开康奈尔大学，担任国家科学基金会助理主任，领导计算机和信息科学与工程理事会。

1989年，Hartmanis被选为美国国家工程院院士，因为他对计算复杂性理论、计算机研究和教育做出了重大贡献。

另外，他还是美国计算机协会和美国数学协会的会员，也是美国国家科学院院士。

1999年5月，密苏里大学授予了他人道主义文学荣誉博士的称号。

1988年，为了纪念Juris Hartmanis 60岁诞辰，由Alan Selman，因对结构复杂性理论的研究而闻名，撰写的一本纪念文集《复杂性理论回顾》（Complexity Theory Retrospective）一书出版。

其中包括若干对Hartmanis的生平和成就的介绍文章。

「计算复杂性」理论奠基人

1965年，Juris Hartmanis和Richard Stearns合作发表了题为《论算法的计算复杂性》On the Computational Complexity of Algorithms 开创性论文，并因此获得了1993年的图灵奖。

这篇论文开辟了计算机科学的一个新的研究领域，即「计算复杂性」（computational complexity），并奠定了它的理论基础。

Hartmanis介绍了他在通用电气开始与Richard Stearns合作进行复杂性研究

在此以前，已有拉宾（M．O．Rabin）、库克（S．A．Cook）、卡普（R．M．Karp）等学者因在计算复杂性理论研究中作出先驱性工作而分别在1976年、1982年和1985年获得图灵奖。

Hartmanis和Stearns则在前人工作的基础上，比较完整地提出了计算复杂性的理论体系，并首次正式命名了「计算复杂性」，因而被公认为计算复杂性理论的主要创始人。

用一句话概括这篇论文的影响，那就是——它使图灵的tape公式经久耐用。

在论文中，他们为图灵机引入了时间复杂度类 TIME (f (n))，并证明了这一时间层次定理。

他们证明了特殊情况下的复杂性层次成为一般理论的计算复杂性。尽管主要使用多带图灵机，但他们认为，这些概念是普遍的，同样的结果会出现在任何合理的模型中。

他们还证明了一些关于模型更改（1-tape、2-tape、1-dim、2-dim ）如何改变 DTIME(T(n)) 概念的定理。

现在，人们已经习惯于这样的概念：我们可以测量在图灵机上计算步数需要的时间。不过，在 Hartmanis-Stearns论文发表之前，人们并不是这么想的。正是他们开启了所谓的复杂性理论。

如果 Hartmanis-Stearns没有开启这一将复杂性置于严格的数学基础上的过程，那么复杂性理论会如何发展？我们可能就无法得出Cook-Levin定理或NP的概念了。

说起让他得到图灵奖的这篇论文，背后还有这样一段有趣的故事。

在1955年，Hartmanis取得了博士学位，进入康乃尔大学数学系任教。

但他在那里只工作了一年多，就转入了通用电气公司。

这一新的领域激发起了Hartmanis极大的兴趣和热情。此时他还没意识到，图灵奖在日后即将向它招手。

当时，香农（Claude Elwood Shanon）的信息论问世不久，香农总结出了一个公式，可以计算在一定的信号和噪声平均功率之下，给定带宽的信道在单位时间内的最大信息传输量（这个公式被叫做「香农公式」）。

念过物理的Hartmanis受此启发，敏锐地想到，抽象的计算过程也应该有精确的定量法则，以确定为了对每一个问题求得解答，需要多少计算工作量。

围绕这一设想，Hartmanis和同事Stearns合作，开展了深入的研究，其结果就是那篇著名的论文《论算法的计算复杂性》。

说起Hartmanis的好搭档Stearns，他会跨进计算机科学的大门并成为一名出色的计算机科学家，还是一件十分偶然的事。

1960年暑假他到通用电气公司打工，被分配到研究实验室新成立的信息研究部，这使他有缘与已成为通用正式职工的Hartmanis一起工作。学过物理而后改行数学的Hartmanis和专攻数学的Stearns开始合作后，双方取长补短，相得益彰，这使他们的合作成果颇丰。

他们的第一个合作课题是关于时序机的状态分派问题。暑假结束时，他们已经完成了一篇合作论文，这就是第二年发表于IRE Trans．on EC的On the state assignment problem for sequential machines。

这次暑期临时工的经历，让Stearns在拿到博士学位后毫不犹豫地应聘到通用电气公司工作，与Hartmanis再度携手，终于再创辉煌，很快完成了奠定计算复杂性理论基础的上述著名论文。不可思议的是，Hartmanis和Stearns在通用电气公司研究计算复杂性的最初几年，实验室里并无计算机可用。这在今天的人们看来简直是不可想象的。

他们当时完全是依靠严密的理论分析才能提出有关计算复杂性的一系列问题，并给出了科学的解释。直到1964年，实验室才配了一台GE 300，他们这才开始用BASIC编程，通过电传打字机接口使用计算机。

在科学技术的发展史上，开创复杂而重要的学科领域并取得巨大成功的学者，最初往往在十分困难的条件下工作，这种情况屡见不鲜。在Hartmanis和Stearns在研究「计算复杂性」理论的过程中，还有一个细节值得一提。

据Stearns本人回忆，他们首次明确提出「计算复杂性」这一名词的论文有过三个版本：最早是1963年4月实验室内部的一个研究报告，没有公开发表；然后是在1964年于普林斯顿举行的IEEE第五届开关电路理论和逻辑设计学术年会上提交的论文，题为「递归序列的计算复杂性」(Computational Complexity of Recursive Sequences)；第三个版本是发表于美国数学会汇刊1965年5月上的「论算法的计算复杂性」（On the Computational Complexity of Algorithms）。

这三个版本中，会议版本虽然早于杂志版本发表，但实际上却是最后一个版本。因为在此之前，他们并不知道Manuel Blum（1995年图灵奖得主）在MIT的博士论文研究的是同一问题；会议之前他们偶然获知这一情况，便立即去MIT拜访了Blum。

当时，Hartmanis和Stearns已是国际知名大公司的研究人员，而Blum则不过是来自南美小国委内瑞拉的青年学子。

曼纽尔·布卢姆（Manuel Blum），1995年图灵奖得主

但Hartmanis和Stearns并不因此而对Blum有任何轻视，并且发现Blum在对「复杂性类」等方面的研究比他们还深入一些，因此对Blum十分推崇，并把他的博士论文列入了他们自己的会议论文的参考文献之中，虽然该博士论文当时尚未公开。

他们这种在学术上平等待人、互相尊重、善于交流的作风，十分令人敬重。

1993年，Hartmanis在接受图灵奖时发了表题为「论计算复杂性及计算机科学的性质」（On Computational Complexity and the Nature of Computer Science）的演说。

1997年，Hartmanis和Leonard Berman在合作的一篇论文中提出了Berman-Hartmanis猜想: 所有 NP 完备语言都是多项式时间同构的。

2022年7月29日，这颗计算机领域的巨星陨落了，但我们会永远记得他为计算机学界留下的宝贵遗产。

参考资料：

https://rjlipton.wpcomstaging.com/2022/07/29/juris-hartmanis-1928-2022/