编辑：张倩
又一颗打算机理论巨星陨落了。
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
