ACM通信
ACM TechNews
法学博士Hartmanis, 1928 - 2022
Hartmanis和Leonard Berman在1977年的一篇论文中介绍了至今仍未解决的Berman - Hartmanis猜想，即所有np完备语言都是多项式时间同构的。
信贷:ACM
1993年美国计算机学会(ACM)图灵奖得主之一、康奈尔大学(Cornell University)计算机科学系教授朱里斯·哈特曼尼斯(Juris Hartmanis)于周五去世，享年94岁。
哈特曼尼斯和理查德·斯特恩斯因他们的论文《论算法的计算复杂度》而获得图灵奖。
加州大学伯克利分校的计算理论家迪克·卡普(Dick Karp)说，这篇论文“标志着复杂性理论现代时代的开始”。使用图灵机作为抽象计算机的模型，[Hartmanis和Stearns]提供了“复杂性类”的精确定义，它包含了所有可在若干步骤内解决的问题，这些步骤以输入长度{n}的某个给定函数为界。利用图灵用来证明中止问题不可解性的对角化技术，他们证明了许多关于复杂类结构的有趣结果。”
从Gödel的丢失的字母和P=NP
查看全文
版权所有©2022SmithBucklin，美国华盛顿特区
没有发现记录