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最终拿到了图灵奖。

阅读详细报道