哈特马尼斯——复杂性理论的重要奠基人

    JurisHartmanis是美国杰出的理论计算机科学家。康奈尔大学计算机科学教授。哈特马尼斯是拉脱维亚人，生于1928年。二战期间，为躲避战火，哈特马尼斯一家人背井离乡，沦为“流民”(displacedperson)。
    1993年，他和理查德·史坦斯（RichardStearns）因对计算复杂性理论的杰出贡献而获得了图灵奖。
    哈特马尼斯于30岁结婚，妻子也是拉脱维亚人，但出生在德国。他们有3个子女。1988年哈特马尼斯60寿辰时，由塞尔曼(A．L．Selman)编辑出版了一本纪念文集《复杂性理论回顾》(ComplexityThe-oryRetrospective，Springer，1988)，其中包括若干对哈特马尼斯的生平和成就的介绍文章。
    哈特马尼斯的中学学业就是在德国哈瑙(Hanau)的难民营中完成的。之后他进入德国马尔布克大学学习物理(Marburg是一座大学城，离法兰克福不远)。两年半之后的1950年，哈特马尼斯获得资助，来到美国，进入堪萨斯城大学攻读硕士学位。但由于该校没有物理学的研究生课程，哈特马尼斯只得改学数学。他用了一年时间取得硕士学位，并被加利福尼亚理工学院接收为博士研究生，从事格论(latticetheory)的研究。4年后，哈特马尼斯完成博士论文，1955年取得博士学位，进入康乃尔大学数学系任教。但他在那里只工作了一年多，就转入通用电气公司设在纽约州斯克内克塔迪(Schenectady)的研究实验室，因为那里新建立了一个“信息研究部”，主任是理查德·舒伊(RichardShuey)博士，开展有关计算机和信息学的研究，这一新的领域激发起了哈特马尼斯极大的兴趣和热情。
    Juris和Audrey当时，香农(ClaudeElwoodShanon)的信息论问世不久，香农给出了一个公式，可以计算在一定的信号和噪声平均功率之下，给定带宽的信道在单位时间内的最大信息传输量(这个公式被叫做“香农公式”)。念过物理的哈特马尼斯受此启发，敏锐地想到，抽象的计算过程也应该有精确的定量法则，以确定为了对每一个问题求得解答，需要多少计算工作量。围绕这一设想哈特马尼斯和曾是普林斯顿大学的研究生，暑假到公司打过工，后来成为他的同事的斯特恩斯合作，开展了深入的研究，其结果就是那篇著名的论文“论算法的计算复杂性”。这篇论文开辟了计算机科学的一个新的研究领域，即“计算复杂性”，并奠定了它的理论基础。
    哈特马尼斯还是著名的Spfinger出版社的《计算机科学讲课笔记》(LectureNotesinComputerScience)系列丛书的主编，这套丛书从20世纪70年代问世以来，至今已推出2000多种专著，许多重要的计算机科学理论问题和新概念、新技术、新方法都是由这套丛书首先提出并展开与深入的，对推动计算机科学技术的发展起了重要作用。