本文发表在 rolia.net 枫下论坛Juris Hartmanis and Richard E. Stearns
Citation
In recognition of their seminal paper which established the foundations for the field of computational complexity theory.
---------------------------
1993年的图灵奖授予合作奠定了计算复杂性理论基础的两位学者尤里斯·哈特马尼斯(Juris Hartmanis)和理查德·斯特恩斯(Richard Edwin Stearns)。在此以前,已有拉宾(M.O.Rabin)、库克(S.A.Cook)、卡普(R.M.Karp)等学者因在计算复杂性理论研究中作出先驱性工作而分别在1976年、1982年和1985年获得图灵奖。哈特尼斯和斯特恩斯则在前人工作的基础上,比较完整地提出了计算复杂性的理论体系,并首次正式命名了“计算复杂性”(computational complexity),因而被公认为计算复杂性理论的主要创始人。
哈特马尼斯是拉脱维亚人,生于1928年。二战期间,为躲避战火,哈特马尼斯一家人背井离乡,沦为“流民”(displaced person)。哈特马尼斯的中学学业就是在德国哈瑙(Hanau)的难民营中完成的。之后他进入德国马尔布克大学学习物理(Marburg是一座大学城,离法兰克福不远八两年半之后的195o年,哈特马尼斯获得资助,来到美国,进人堪萨斯城大学攻读硕士学位。但由于该校没有物理学的研究生课程,哈特马尼斯只得改学数学。他用了一年时间取得硕士学位,并被加利福尼亚理工学院接收为博士研究生,从事格论(lattice theory)的研究。4年后,哈特马尼斯完成博士论文,1955年取得博士学位,进入康乃尔大学数学系任教。但他在那里只工作了一年多,就转入通用电气公司设在纽约州斯克内克塔迪(Schenectady)的研究实验室,因为那里新建立了一个“信息研究部”,主任是理查德·舒伊(Richard Shuey)博士,开展有关计算机和信息学的研究,这一新的领域激发起了哈特马尼斯极大的兴趣和热情。
当时,香农(Claude Elwood Shanon)的信息论问世不久,香农结出了一个公式,可以计算在一定的信号和噪声平均功率之下,给定带宽的信道在单位时间内的最大信息传输量(这个公式被叫做“香农公式”)。念过物理的哈特马尼斯受此启发,敏锐地想到,抽象的计算过程也应该有精确的定量法则,以确定为了对每一个问题求得解答,需要多少计算工作量。围绕这一设想哈特马尼斯和曾是普林斯顿大学的研究生,暑假到公司打过工,后来成为他的同事的斯特恩斯合作,开展了深入的研究,其结果就是那篇著名的论文“论算法的计算复杂性”(On the computational complexity of algorithms,Trams. Amer.Math.Soc.,177(1965),285-306页)。这篇论文开辟了计算机科学的一个新的研究领域,即“计算复杂性”,并奠定了它的理论基础。关于计算复杂性,本书前面已经作过一些简要的介绍,这里不再重复。
哈特马尼斯于1965年离开通用电气公司,重返康乃尔大学,但不是回到数学系,而是负责筹建计算机科学系。由于他的眼光和魄力,也由于他的民主作风,康乃尔大学的计算机科学系吸引了一批著名学者加盟,成为美国大学中水平最高、影响最大的计算机科学系之一。这些学者中包括霍普克洛夫特(J.E.Hoperof,1986年图灵奖得主)、格利斯(D.Gries,1995年ACM优秀计算机教育奖获得者)、霍洛维茨(E.Horowitz)、韦格纳(P.Wegner)和肖(A.Shaw)等。
20世纪90年代,哈特马尼斯曾经完成一项重要的工作。1990年4月,美国科学研究委员会(National Research Council)的计算机科学与技术部(现已改为计算机科学与通信部,缩写CSTB)建立了一个由16名专家组成的委员会,负责对计算机科学与技术在未来的对世纪中的发展方向和研究领域进行评估(Committee to Assess the Scope and Direction of Computer Science and Technology)。哈特马尼斯受命担任该委员会主席。委员中包括另外两名图灵奖获得者雷迪(R.Reddy)和格雷(J.Gray)。哈特马尼斯组织委员会委员和来自全美的 120余名学者共同努力,于1992年编写出版了《未来的计算——计算机科学与技术的广泛议题》(Computing the Future——A Broader AgendaF0r Computer Science and Engineering)一书。本书对 ZI世纪计算机科学与工程的研究、教育等重大课题进行了分析,对政府、产、学、研各部门如何适应新形势提出了一系列重要意见和看法,很值得我国科研管理部门和信息产业高层决策者重视。这本书和我们前面曾经提到的由米尔纳(R.Milner,1991年图灵奖获得者)等主编的《明天的计算:计算机科学未来的研究方向》(Computing Tomorrow : Future Research Directions in Computer Science,Combridge Uni.Pr.,1996)可以看作是姊妹篇。
哈特马尼斯论著极多,除大量发表于杂志和会议的论文外,出版的主要著作有:
《时序机的代数结构理论》(Algebraic Structure Theory of Sequential Machines,Prentice-Hall,1966)
《可行计算和可证明的复杂性性质》(Feasible Computations and Provable Complexity Properties, SIAM,1978)
《计算机复杂性理论》(Computational Complexity Theory,AMS,1989)
哈特马尼斯还是著名的Springer出版社的《计算机科学讲课笔记》。(Lecture Notes in Computer Science)系列丛书的主编,这套丛书从 20世纪70年代问世以来,至今已推出2000多种专著,许多重要的计算机科学理论问题和新概念、新技术、新方法都是由这套丛书首先提出并展开与深入的,对推动计算机科学技术的发展起了重要作用。
哈特马尼斯于3O岁结婚,妻子也是拉脱维亚人,但出生在德国。他们有3个子女。1988年哈特马尼斯60寿辰时,由塞尔曼(A.L.Selman)编辑出版了一本纪念文集《复杂性理论回顾》(Complexity Theory Retrospective,Springer,1988),其中包括若干对哈特马尼斯的生平和成就的介绍文章。
与哈特马尼斯合作并共同获奖的斯特恩斯也是学数学的,1936年7月5日出生于新泽西州的卡特维尔(Caldwell)。1958年他在卡尔顿学院(Carton College)取得数学学士学位后进入普林斯顿大学,用了3年时间取得博士学位,其博士论文课题是关于博奕论的。
斯特恩斯跨进计算机科学的大门并成为一名出色的计算机科学家是十分偶然的。1960年暑假他到通用电气公司打工,被分配到研究实验室新成立的信息研究部,这使他有缘与已成为那里正式职工的哈特马尼斯一起工作。学过物理而后改行数学的哈特马尼斯和专攻数学的斯特恩斯相结合,双方取长补短,相得益彰,使他们的合作富有成果。他们的第一个合作课题是关于时序机的状态分派问题的。这项研究进行得十分顺利,暑假打工结束时,他们已经完成了第、篇合作论文,这就是第二年发表于IRE Trans.on EC的On the state assignment problem for sequential machines(IRE-EC,1961年 12月,593-603页)。暑期临时工的经历虽然十分短暂,所做课题也和他的博士论文无关,但通用电气公司研究人员的素质和才能,那里浓郁、自由。活泼的学术空气,以及新的、充满机会的学科领域给斯特恩斯留下了十分深刻的印象。因此,一年后他一拿到博士学位,立刻毫不犹豫地应聘到通用电气公司工作,与哈特马尼斯再度携手,终于再创辉煌,很快完成了奠定计算复杂性理论基础的上述著名论文。
说来有趣,斯特恩斯和哈特马尼斯在通用电气公司研究计算复杂性的最初几年,实验室里并无计算机可用。他们当时完全是依靠严密的理论分析提出有关计算复杂性的一系列问题,并给出了科学的解释的。直到1964年,实验室才配了一台GE 300,斯特恩斯这才开始用BASIC编程,通过电传打字机接口使用计算机。在科学技术的发展史上,开创复杂而重要的学科领域并取得巨大成功的学者,最初往往在十分困难的条件下工作,这种情况是屡见不鲜的。
斯特恩斯和哈特马尼斯在研究“计算复杂性”理论的过程中,还有一个细节值得一提。据斯特恩斯本人回忆,他们首次明确提出“计算复杂性”这一名词的论文有过三个版本:最早是1963年4月实验室内部的一个研究报告,没有公开发表;然后是在1964年于普林斯顿举行的IEEE第五届开关电路理论和逻辑设计学术年会上提交的论文,题为“递归序列的计算复杂性”(Computational Complexity of Recursive Sequences),刊于会议论文集 82- 90页。第三个版本是发表于美国数学会汇刊1965年5月上的“论算法的计算复杂性”(on the Computational Complexity of Algorithms)。这三个版本中,会议版本虽然早于杂志版本发表,但实际上却是最后一个版本。因为在此之前,他们对布卢姆(M.Blum,1995年图灵奖得主)在MIT的博士论文研究的是同样问题并无所知;会议之前他们偶然获知这一情况,便立即去MIT拜访了布卢姆,双方进行了交流。当时,哈特马尼斯和斯特恩斯已是国际知名大公司的研究人员,而布卢姆则不过是来自南美洲的小国委内瑞拉的青年学子。但哈特马尼斯和斯特恩斯并不因此而对布卢姆有任何轻视,并且发现布卢姆在对“复杂性类”等方面的研究比自己还深入一些,因此对布卢姆十分推崇,并把他的博士论文列入了他们自己的会议论文的参考文献之中,虽然该博士论文当时尚未公开与发表。他们这种在学术上平等待人,互相尊重,善于交流的作风是很可贵和值得学习的。
斯特恩斯后来除了在“计算复杂性”理论上继续有建树并发表了许多论文外,还对编译器的设计与理论进行深入的研究并取得了成果。1976年,斯特恩斯最先提出将上下文无关文法的理论应用于编译器的设计,推动了编译器技术的发展。他和刘易斯(P.M.Lewis)以及罗深克拉茨(D.J.Rosenkratz)合著的 Compiler Design Theory一书(Addison-Wesley,1976)被软件界认为是“编译器设计理论”方面最出色的专著之一。他和奥曼(R.J.Aumann)以及马须勒(M.B.Maschler)合著的《带不完备信息的可重复游戏》(Repeated Games with Incomplete Information, MIT Pr.,1995)则因在运筹学方间的杰出贡献而荣获当年的Lanchster奖。
哈特马尼斯在接受图灵奖时发表及题为“论计算复杂性及计算机科学的性质”(On Computational Complexity and the Nature of Computer Science)的演说,刊载于 Comm.ACM,37(10):37-43页(Oct 1994)。
斯特恩斯在接受图灵奖时发表了题为“是重新考虑时间这个问题的时候了”(It’s Time to Reconsider Time)的演说。演说中概括了他和哈特马尼斯以及布卢姆共同奠定了计算复杂性理论的基础以来,这一重要领域所取得的主要进展。关心这一领域的读者不妨一阅。演说全文刊载于1994年11月的 Communications of ACM, 95- 99页。
哈特马尼斯的电子信箱为jh @ cs.cornell.edu。
斯特恩斯现为奥尔巴尼纽约州立大学计算机科学系教授,其电子信箱为:
res@ cs.albany.edu更多精彩文章及讨论,请光临枫下论坛 rolia.net
Citation
In recognition of their seminal paper which established the foundations for the field of computational complexity theory.
---------------------------
1993年的图灵奖授予合作奠定了计算复杂性理论基础的两位学者尤里斯·哈特马尼斯(Juris Hartmanis)和理查德·斯特恩斯(Richard Edwin Stearns)。在此以前,已有拉宾(M.O.Rabin)、库克(S.A.Cook)、卡普(R.M.Karp)等学者因在计算复杂性理论研究中作出先驱性工作而分别在1976年、1982年和1985年获得图灵奖。哈特尼斯和斯特恩斯则在前人工作的基础上,比较完整地提出了计算复杂性的理论体系,并首次正式命名了“计算复杂性”(computational complexity),因而被公认为计算复杂性理论的主要创始人。
哈特马尼斯是拉脱维亚人,生于1928年。二战期间,为躲避战火,哈特马尼斯一家人背井离乡,沦为“流民”(displaced person)。哈特马尼斯的中学学业就是在德国哈瑙(Hanau)的难民营中完成的。之后他进入德国马尔布克大学学习物理(Marburg是一座大学城,离法兰克福不远八两年半之后的195o年,哈特马尼斯获得资助,来到美国,进人堪萨斯城大学攻读硕士学位。但由于该校没有物理学的研究生课程,哈特马尼斯只得改学数学。他用了一年时间取得硕士学位,并被加利福尼亚理工学院接收为博士研究生,从事格论(lattice theory)的研究。4年后,哈特马尼斯完成博士论文,1955年取得博士学位,进入康乃尔大学数学系任教。但他在那里只工作了一年多,就转入通用电气公司设在纽约州斯克内克塔迪(Schenectady)的研究实验室,因为那里新建立了一个“信息研究部”,主任是理查德·舒伊(Richard Shuey)博士,开展有关计算机和信息学的研究,这一新的领域激发起了哈特马尼斯极大的兴趣和热情。
当时,香农(Claude Elwood Shanon)的信息论问世不久,香农结出了一个公式,可以计算在一定的信号和噪声平均功率之下,给定带宽的信道在单位时间内的最大信息传输量(这个公式被叫做“香农公式”)。念过物理的哈特马尼斯受此启发,敏锐地想到,抽象的计算过程也应该有精确的定量法则,以确定为了对每一个问题求得解答,需要多少计算工作量。围绕这一设想哈特马尼斯和曾是普林斯顿大学的研究生,暑假到公司打过工,后来成为他的同事的斯特恩斯合作,开展了深入的研究,其结果就是那篇著名的论文“论算法的计算复杂性”(On the computational complexity of algorithms,Trams. Amer.Math.Soc.,177(1965),285-306页)。这篇论文开辟了计算机科学的一个新的研究领域,即“计算复杂性”,并奠定了它的理论基础。关于计算复杂性,本书前面已经作过一些简要的介绍,这里不再重复。
哈特马尼斯于1965年离开通用电气公司,重返康乃尔大学,但不是回到数学系,而是负责筹建计算机科学系。由于他的眼光和魄力,也由于他的民主作风,康乃尔大学的计算机科学系吸引了一批著名学者加盟,成为美国大学中水平最高、影响最大的计算机科学系之一。这些学者中包括霍普克洛夫特(J.E.Hoperof,1986年图灵奖得主)、格利斯(D.Gries,1995年ACM优秀计算机教育奖获得者)、霍洛维茨(E.Horowitz)、韦格纳(P.Wegner)和肖(A.Shaw)等。
20世纪90年代,哈特马尼斯曾经完成一项重要的工作。1990年4月,美国科学研究委员会(National Research Council)的计算机科学与技术部(现已改为计算机科学与通信部,缩写CSTB)建立了一个由16名专家组成的委员会,负责对计算机科学与技术在未来的对世纪中的发展方向和研究领域进行评估(Committee to Assess the Scope and Direction of Computer Science and Technology)。哈特马尼斯受命担任该委员会主席。委员中包括另外两名图灵奖获得者雷迪(R.Reddy)和格雷(J.Gray)。哈特马尼斯组织委员会委员和来自全美的 120余名学者共同努力,于1992年编写出版了《未来的计算——计算机科学与技术的广泛议题》(Computing the Future——A Broader AgendaF0r Computer Science and Engineering)一书。本书对 ZI世纪计算机科学与工程的研究、教育等重大课题进行了分析,对政府、产、学、研各部门如何适应新形势提出了一系列重要意见和看法,很值得我国科研管理部门和信息产业高层决策者重视。这本书和我们前面曾经提到的由米尔纳(R.Milner,1991年图灵奖获得者)等主编的《明天的计算:计算机科学未来的研究方向》(Computing Tomorrow : Future Research Directions in Computer Science,Combridge Uni.Pr.,1996)可以看作是姊妹篇。
哈特马尼斯论著极多,除大量发表于杂志和会议的论文外,出版的主要著作有:
《时序机的代数结构理论》(Algebraic Structure Theory of Sequential Machines,Prentice-Hall,1966)
《可行计算和可证明的复杂性性质》(Feasible Computations and Provable Complexity Properties, SIAM,1978)
《计算机复杂性理论》(Computational Complexity Theory,AMS,1989)
哈特马尼斯还是著名的Springer出版社的《计算机科学讲课笔记》。(Lecture Notes in Computer Science)系列丛书的主编,这套丛书从 20世纪70年代问世以来,至今已推出2000多种专著,许多重要的计算机科学理论问题和新概念、新技术、新方法都是由这套丛书首先提出并展开与深入的,对推动计算机科学技术的发展起了重要作用。
哈特马尼斯于3O岁结婚,妻子也是拉脱维亚人,但出生在德国。他们有3个子女。1988年哈特马尼斯60寿辰时,由塞尔曼(A.L.Selman)编辑出版了一本纪念文集《复杂性理论回顾》(Complexity Theory Retrospective,Springer,1988),其中包括若干对哈特马尼斯的生平和成就的介绍文章。
与哈特马尼斯合作并共同获奖的斯特恩斯也是学数学的,1936年7月5日出生于新泽西州的卡特维尔(Caldwell)。1958年他在卡尔顿学院(Carton College)取得数学学士学位后进入普林斯顿大学,用了3年时间取得博士学位,其博士论文课题是关于博奕论的。
斯特恩斯跨进计算机科学的大门并成为一名出色的计算机科学家是十分偶然的。1960年暑假他到通用电气公司打工,被分配到研究实验室新成立的信息研究部,这使他有缘与已成为那里正式职工的哈特马尼斯一起工作。学过物理而后改行数学的哈特马尼斯和专攻数学的斯特恩斯相结合,双方取长补短,相得益彰,使他们的合作富有成果。他们的第一个合作课题是关于时序机的状态分派问题的。这项研究进行得十分顺利,暑假打工结束时,他们已经完成了第、篇合作论文,这就是第二年发表于IRE Trans.on EC的On the state assignment problem for sequential machines(IRE-EC,1961年 12月,593-603页)。暑期临时工的经历虽然十分短暂,所做课题也和他的博士论文无关,但通用电气公司研究人员的素质和才能,那里浓郁、自由。活泼的学术空气,以及新的、充满机会的学科领域给斯特恩斯留下了十分深刻的印象。因此,一年后他一拿到博士学位,立刻毫不犹豫地应聘到通用电气公司工作,与哈特马尼斯再度携手,终于再创辉煌,很快完成了奠定计算复杂性理论基础的上述著名论文。
说来有趣,斯特恩斯和哈特马尼斯在通用电气公司研究计算复杂性的最初几年,实验室里并无计算机可用。他们当时完全是依靠严密的理论分析提出有关计算复杂性的一系列问题,并给出了科学的解释的。直到1964年,实验室才配了一台GE 300,斯特恩斯这才开始用BASIC编程,通过电传打字机接口使用计算机。在科学技术的发展史上,开创复杂而重要的学科领域并取得巨大成功的学者,最初往往在十分困难的条件下工作,这种情况是屡见不鲜的。
斯特恩斯和哈特马尼斯在研究“计算复杂性”理论的过程中,还有一个细节值得一提。据斯特恩斯本人回忆,他们首次明确提出“计算复杂性”这一名词的论文有过三个版本:最早是1963年4月实验室内部的一个研究报告,没有公开发表;然后是在1964年于普林斯顿举行的IEEE第五届开关电路理论和逻辑设计学术年会上提交的论文,题为“递归序列的计算复杂性”(Computational Complexity of Recursive Sequences),刊于会议论文集 82- 90页。第三个版本是发表于美国数学会汇刊1965年5月上的“论算法的计算复杂性”(on the Computational Complexity of Algorithms)。这三个版本中,会议版本虽然早于杂志版本发表,但实际上却是最后一个版本。因为在此之前,他们对布卢姆(M.Blum,1995年图灵奖得主)在MIT的博士论文研究的是同样问题并无所知;会议之前他们偶然获知这一情况,便立即去MIT拜访了布卢姆,双方进行了交流。当时,哈特马尼斯和斯特恩斯已是国际知名大公司的研究人员,而布卢姆则不过是来自南美洲的小国委内瑞拉的青年学子。但哈特马尼斯和斯特恩斯并不因此而对布卢姆有任何轻视,并且发现布卢姆在对“复杂性类”等方面的研究比自己还深入一些,因此对布卢姆十分推崇,并把他的博士论文列入了他们自己的会议论文的参考文献之中,虽然该博士论文当时尚未公开与发表。他们这种在学术上平等待人,互相尊重,善于交流的作风是很可贵和值得学习的。
斯特恩斯后来除了在“计算复杂性”理论上继续有建树并发表了许多论文外,还对编译器的设计与理论进行深入的研究并取得了成果。1976年,斯特恩斯最先提出将上下文无关文法的理论应用于编译器的设计,推动了编译器技术的发展。他和刘易斯(P.M.Lewis)以及罗深克拉茨(D.J.Rosenkratz)合著的 Compiler Design Theory一书(Addison-Wesley,1976)被软件界认为是“编译器设计理论”方面最出色的专著之一。他和奥曼(R.J.Aumann)以及马须勒(M.B.Maschler)合著的《带不完备信息的可重复游戏》(Repeated Games with Incomplete Information, MIT Pr.,1995)则因在运筹学方间的杰出贡献而荣获当年的Lanchster奖。
哈特马尼斯在接受图灵奖时发表及题为“论计算复杂性及计算机科学的性质”(On Computational Complexity and the Nature of Computer Science)的演说,刊载于 Comm.ACM,37(10):37-43页(Oct 1994)。
斯特恩斯在接受图灵奖时发表了题为“是重新考虑时间这个问题的时候了”(It’s Time to Reconsider Time)的演说。演说中概括了他和哈特马尼斯以及布卢姆共同奠定了计算复杂性理论的基础以来,这一重要领域所取得的主要进展。关心这一领域的读者不妨一阅。演说全文刊载于1994年11月的 Communications of ACM, 95- 99页。
哈特马尼斯的电子信箱为jh @ cs.cornell.edu。
斯特恩斯现为奥尔巴尼纽约州立大学计算机科学系教授,其电子信箱为:
res@ cs.albany.edu更多精彩文章及讨论,请光临枫下论坛 rolia.net