1993 尤里斯·哈特马尼斯

shiyi18

Juris Hartmanis
BIRTH:
July 5, 1928 in Riga, Latvia

EDUCATION:
Cand. Phil., University of Marburg (1949, Physics); M.A., University of Kansas City (1951, Mathematics); Ph.D., California Institute. of Technology (1955, Mathematics)

EXPERIENCE:
Instructor, Cornell University (1955-1957); Assistant Professor, Ohio State University (1957-1958); Research Mathematician, General Electric Research Laboratory (1958-1965); Professor, Computer Science Department, Cornell University (1965-); Chairman, Computer Science Department, Cornell University (1965-1971, again 1977-1982, and 1992-1993); Walter R. Read Professor of Engineering, Cornell University (from 1980)

HONORS AND AWARDS:
Association for Computing Machinery Turing Award (with R.E. Stearns), 1993; Member: National Academy of Engineering, 1989; Member: Latvian Academy of Sciences, 1990 (foreign member); Member: New York State Academy of Sciences, 1982; Fellow: Association for Computing Machinery, 1994; Fellow: American Academy of Arts & Sciences, 1992; Fellow: American Association for the Advancement of Science, 1981; Humboldt Foundation Senior US Scientist Award, 1993-94; B. Blozano Gold Medal of the Academy of Sciences, Czech Republic, 1995; CRA Distinguished Service Award, 2000; Grand Medal, Latvian Academy of Science, 2001; he also has received two honorary doctorates: University of Dortmund, Germany, 1995, and University of Missouri, Kansas City, 1999.


JURIS HARTMANIS DL Author Profile link
United States – 1993
CITATION
With Richard E. Stearns, in recognition of their seminal paper which established the foundations for the field of computational complexity theory.

SHORT ANNOTATED
BIBLIOGRAPHY
ACM TURING AWARD
LECTURE
RESEARCH
SUBJECTS
ADDITIONAL
MATERIALS
VIDEO INTERVIEW
Juris Hartmanis was the son of a senior Latvian army officer who was arrested when the Soviet Union occupied Latvia during World War II and subsequently died in prison.

Hartmanis discusses the death of his father following the Soviet occupation of Lithuania in 1940.       
At the end of the War, the remaining members of the family moved to Germany where Juris obtained an undergraduate degree in physics from the University of Marburg in 1949. He then moved to the United States to begin graduate work and eventually received an MA in 1951 and a PhD in 1955, both in mathematics.

Juris began his career with posts as an Instructor at Cornell University (1955–1957) and later as an Assistant Professor at Ohio State University (1957–1958). He then took a position as a Research Mathematician at General Electric Research Laboratory, which lasted for ten years.

In the last few years of his time at General Electric, he and Richard Stearns became interested in how much time and memory are needed to perform different computations – a field that they named computational complexity. They defined different classes of calculations according to how much calculation and/or memory space each would require, which is a measure of their difficulty. Their famous 1965 joint paper [7] began to interest other computer scientists in looking at complexity the same way.

Hartmanis discusses his decade working for General Electric where he began his collaboration with Dick Stearns on complexity research.       
In contrast to other approaches to complexity theory, Hartmanis and Sterns based their analysis on measuring the resources that algorithms use when run on specific machines. In order to have some generality, they used a Turing Machine as their basic model. They were pleasantly surprised to discover a number of important mathematical theorems related to complexity analysis.

The full Turing Award citation for Hartmanis and Stearns notes:

In their paper On the Computational Complexity of Algorithms they provided a precise definition of the complexity measure defined by computation time on Turing machines and developed a theory of complexity classes. The paper sparked the imagination of many computer scientists and led to the establishment of complexity theory as a fundamental part of the discipline.

They introduced a basic concept called a computational complexity class. Informally, a class represents all the computations that can be done using a given amount of resources. For example, an individual class might contain all problems that use N2 steps, where N is the size of the problem. Some of today’s most important theoretical problem areas are the relations between these classes, such as the relation between the class of problems that can be solved in an amount of time that can be expressed as a polynomial function of N, and those that scale more quickly than can be represented by a polynomial. The classic unsolved P=NP problem asks whether there are problems whose answers can checked in polynomial time but will always take longer to solve, no matter how clever we are.

Hartmanis discusses his work with Stearns to define complexity classes and its relationship to Turing machine experiments.       
Hartmanis’ work on the foundations of complexity theory was instrumental in establishing computer science as a formal discipline distinct from mathematics, physics and electrical engineering. In the context of later work by Michael Rabin, Manuel Blum and others, Hartmanis and Stearns, in their seminal 1964 (conference) and 1965 (journal) papers [5, 6], provided the basis for the development of complexity theory as it is now studied. In particular, they showed how Turing’s work in defining the limitations of “what is computable” could be extended to a model for “what is efficiently computable”.

Many seminal results and insights were included in these two influential early papers. The multi-tape Turing machine was shown to be a precise and helpful model for sequential time complexity analysis. They showed the importance of asymptotic behavior, and the use and extension of Yamada’s real time counting functions [1] to establish the existence of a hierarchy of complexity classes.

The time-bounded complexity results were soon followed by a Lewis, Stearns and Hartmanis paper [8]  establishing a similar hierarchy for space-bounded computation. In addition to the tighter hierarchy results, this paper defined a precise concept for sublinear space, and showed that problems such as context free language recognition could be solved with O(log2 n) space. The divide-and-conquer method used in this result was the starting point for John E. Savage’s deterministic S2 space simulation of any non-deterministic space S ≥ log n computation. This in turn led to simulations of the tradeoff between parallel time and space, reinforcing the importance of sublinear space and the question of whether or not non-deterministic space can be deterministically simulated without any loss of efficiency.

Hartmanis discusses work on the P=NP problem and its relationship to nondeterminism carried out with Neil Immerman.       
Hartmanis established complexity theory as the dominant theme in theoretical computer science with his major results concerning the structural nature of NP sets. In particular, he explored the question of whether or not all NP complete sets were isomorphic, i.e., whether all NP complete sets are basically the same set.Hartmanis and his student Leonard C. Berman showed that all natural NP complete sets are isomorphic (under polynomial time reductions), and further showed that complete sets computable in exponential time cannot be sparse.

This Berman–Hartmanis conjecture is important. As Hartmanis himself explained it:

We conjectured that they are polynomial time isomorphic, which is a strictly defined term; that in structure they are basically identical—that one is just a permutation of another. And in some sense this conjecture could be used to date what is now known as structural complexity theory. And structural complexity theory refers to relating the structure of the different complexity class to each other. So one does not ask about less specific algorithms, but more interested in what are big, more global, structural relationships, like the question of do all NP complete sets really look the same, or are there different ones. [2]

Hartmanis’ seminal research paralleled his leadership as chair of the Cornell computer science department and his active participation in numerous advisory boards.

Hartmanis believes that computational complexity—the study of the quantitative laws that govern computation—is an essential part of the science needed to guide and exploit computer technology.

Author: Allan Borodin


[1] H. Yamada, “Real-time computation and recursive functions not real-time computable,” IRE Transactions, EC-ll (1962), pp. 753-760.

[2] From an IEEE transcript of an oral history interview of Juris Hartmanis conducted in 1991 by Andrew Goldstine, IEEE History Center, New Brunswick, NJ, USA, available from

http://www.ieeeghn.org/wiki/inde ... ory:Juris_Hartmanis



Juris Hartmanis
出生地
1928年7月5日生于拉脱维亚的里加

学历。
马堡大学博士（1949年，物理学）；堪萨斯大学硕士（1951年，数学）。马尔堡大学哲学博士（1949年，物理学）；堪萨斯大学文学硕士（1951年，数学）；加州理工学院博士（1955年，数学）。

工作经验。
康奈尔大学讲师（1955-1957）；俄亥俄州立大学助理教授（1957-1958）；通用电气研究实验室数学家（1958-1965）；康奈尔大学计算机科学系教授（1965-）；康奈尔大学计算机科学系主任（1965-1971，1977-1982和1992-1993）；康奈尔大学Walter R. Read工程教授（从1980开始）。

荣誉和奖项。
计算机协会图灵奖（与R.E. Stearns一起），1993；成员。国家工程院，1989年；成员。拉脱维亚科学院，1990年（外国成员）；成员。1982年，纽约州科学院；1994年，计算机协会研究员。计算机协会，1994年；研究员。美国艺术与科学学院研究员，1992年；美国科学促进会研究员。1981年，美国科学促进会；1993-94年，洪堡基金会美国高级科学家奖；1995年，捷克共和国科学院B.Blozano金奖；2000年，CRA杰出服务奖；2001年，拉脱维亚科学院大勋章；他还获得了两个荣誉博士学位。1995年，德国多特蒙德大学；1999年，密苏里大学堪萨斯城分校。


JURIS HARTMANIS DL作者简介链接
美国 - 1993年
参考文献
与Richard E. Stearns合作，以表彰他们的开创性论文，该论文为计算复杂性理论领域奠定了基础。

简短注释
书目
亚马逊图灵奖
讲座
研究
主题
额外的
材料
采访视频
尤里斯-哈特曼尼斯是一位拉脱维亚高级军官的儿子，他在二战期间苏联占领拉脱维亚时被捕，随后死于狱中。

哈特曼尼斯讨论了他父亲在1940年苏联占领立陶宛后的死亡情况。       
战争结束后，家庭的其余成员搬到了德国，朱利斯于1949年在马尔堡大学获得了物理学的本科学位。然后他搬到美国开始研究生工作，最终在1951年获得硕士学位，1955年获得博士学位，都是数学专业。

尤里斯开始了他的职业生涯，在康奈尔大学担任讲师（1955-1957），后来在俄亥俄州立大学担任助理教授（1957-1958）。然后他在通用电气研究实验室担任研究数学家的职位，持续了十年。

在通用电气的最后几年里，他和理查德-斯泰恩斯对进行不同的计算需要多少时间和内存产生了兴趣--他们把这个领域命名为计算复杂性。他们根据每个计算需要多少计算和/或内存空间来定义不同类别的计算，这是衡量其难度的一个标准。他们在1965年发表的著名的联合论文[7]开始引起其他计算机科学家的兴趣，以同样的方式来看待复杂性。

Hartmanis讨论了他在通用电气工作的十年，在那里他开始与Dick Stearns合作进行复杂性研究。       
与其他复杂性理论的方法不同，Hartmanis和Sterns的分析是基于测量算法在特定机器上运行时使用的资源。为了有一定的通用性，他们使用图灵机作为他们的基本模型。他们惊喜地发现了一些与复杂性分析有关的重要数学定理。

哈特曼尼斯和斯特恩斯的图灵奖引文全文指出。

在他们的论文《论算法的计算复杂性》中，他们提供了一个由图灵机上的计算时间定义的复杂性度量的精确定义，并发展了一个复杂性类别的理论。这篇论文激发了许多计算机科学家的想象力，并导致复杂性理论被确立为该学科的一个基本组成部分。

他们引入了一个基本概念，叫做计算复杂性类。非正式地讲，一个类代表了使用给定数量的资源可以完成的所有计算。例如，一个单独的类可能包含所有使用N2步骤的问题，其中N是问题的大小。今天一些最重要的理论问题领域是这些类之间的关系，比如可以在一定时间内解决的问题类与那些扩展速度超过可以用多项式函数表示的问题之间的关系。经典的未解决的P=NP问题问的是，是否有一些问题的答案可以在多项式时间内检查出来，但无论我们多么聪明，总是需要更长的时间来解决。

Hartmanis讨论了他与Stearns一起定义复杂性类别的工作，以及它与图灵机实验的关系。       
哈特曼尼斯在复杂性理论基础方面的工作对建立计算机科学作为一门有别于数学、物理学和电子工程的正式学科起到了重要作用。在后来Michael Rabin、Manuel Blum等人的工作中，Hartmanis和Stearns在其1964年（会议）和1965年（期刊）的开创性论文中[5, 6]，为现在研究的复杂性理论的发展提供了基础。特别是，他们展示了图灵在定义 "什么是可计算的 "的限制方面的工作是如何扩展到 "什么是可有效计算的 "的模型。

这两篇有影响的早期论文中包含了许多开创性的结果和见解。多带图灵机被证明是顺序时间复杂性分析的一个精确而有用的模型。他们展示了渐进行为的重要性，以及使用和扩展Yamada的实时计数函数[1]来建立复杂性类的层次结构。

很快，Lewis, Stearns和Hartmanis的论文[8]确立了空间约束计算的类似层次结构，这是有时间约束的复杂性结果。除了更严格的层次结果之外，这篇论文还定义了亚线性空间的精确概念，并表明诸如无语境语言识别等问题可以用O(log2 n)空间来解决。这个结果中使用的分割和征服方法是John E. Savage对任何非确定性空间S≥log n计算的确定性S2空间模拟的起点。这又导致了对并行时间和空间之间的权衡的模拟，加强了亚线性空间的重要性，以及非确定性空间是否可以在不损失效率的情况下进行确定性模拟的问题。

Hartmanis讨论了与Neil Immerman一起进行的关于P=NP问题及其与非确定性的关系的工作。       
哈特曼尼斯以其关于NP集的结构性质的主要成果，将复杂性理论确立为理论计算机科学的主导主题。特别是，他探讨了所有NP完整集是否同构的问题，即所有NP完整集是否基本上是同一个集合。Hartmanis和他的学生Leonard C. Berman表明，所有自然NP完整集是同构的（在多项式时间还原下），并进一步表明，可在指数时间内计算的完整集不可能是稀疏的。

这个Berman-Hartmanis猜想很重要。正如哈特曼尼斯自己解释的那样。

我们猜想它们是多项式时间同构的，这是一个严格定义的术语；在结构上它们基本上是相同的，一个只是另一个的置换。从某种意义上说，这个猜想可以用来确定现在被称为结构复杂性理论的东西。而结构复杂性理论指的是将不同复杂性类别的结构相互联系起来。因此，人们不问不太具体的算法，而是对什么是大的、更全局的、结构性的关系更感兴趣，比如所有的NP完全集是否真的看起来一样，还是有不同的。[2]

哈特曼尼斯的开创性研究与他作为康奈尔大学计算机科学系主任的领导地位和他积极参与众多咨询委员会的工作相一致。

哈特曼尼斯认为，计算复杂性--对支配计算的定量规律的研究--是指导和利用计算机技术所需的科学的一个重要部分。

作者。阿兰-鲍罗廷


[1] H. Yamada, "实时计算和不可实时计算的递归函数，" IRE Transactions, EC-ll (1962), pp.753-760.

[2] 摘自1991年Andrew Goldstine对Juris Hartmanis的口述历史访谈的IEEE记录，IEEE历史中心，美国新泽西州新不伦瑞克，可从以下网址获取

http://www.ieeeghn.org/wiki/inde ... ory:Juris_Hartmanis