Juris Hartmanis
Encyclopedia
Juris Hartmanis is a prominent computer scientist
and computational theorist who, with Richard E. Stearns
, received the 1993 ACM
Turing Award
"in recognition of their seminal paper which established the foundations for the field of computational complexity theory
".
Hartmanis was born in Latvia
. He was a son of Mārtiņš Hartmanis, a general in the Latvian Army. After the Soviet Union occupied Latvia in 1940
, Mārtiņš Hartmanis was arrested by Soviets and died in a prison. At the end of World War II
, the wife and children of Mārtiņš Hartmanis left Latvia as refugees, fearing for their safety if the Soviet Union took over Latvia again.
They first moved to Germany
, where Juris Hartmanis received the equivalent of a Bachelor's degree
in Physics from the University of Marburg. Then he moved to the United States
, where he received Master's degree
in Applied Mathematics at the University of Kansas City (now known as the University of Missouri-Kansas City) in 1951 and Ph.D.
in Mathematics from Caltech under the supervision of Robert P. Dilworth
in 1955. The University of Missouri-Kansas City honored him with Honorary Doctor of Humane Letters in May 1999.
After teaching at Cornell University
and Ohio State University
, Hartmanis joined the General Electric
Research Laboratory in 1958. While at General Electric, he developed many principles of computational complexity theory. In 1965, he became a professor at Cornell University
. At Cornell, he was one of founders and the first chairman of its computer science
department (which was one of the first computer science departments in the world). Hartmanis is a Fellow
of the Association for Computing Machinery
and a member of National Academy of Engineering
.
He is best known for his Turing-award winning paper with Richard Stearns, in which he introduced time complexity
classes TIME (f(n))
and proved the time hierarchy theorem
.
Computer scientist
A computer scientist is a scientist who has acquired knowledge of computer science, the study of the theoretical foundations of information and computation and their application in computer systems....
and computational theorist who, with Richard E. Stearns
Richard Stearns (computer scientist)
Richard Edwin Stearns is a prominent computer scientist who, with Juris Hartmanis, received the 1993 ACM Turing Award "in recognition of their seminal paper which established the foundations for the field of computational complexity theory"...
, received the 1993 ACM
Association for Computing Machinery
The Association for Computing Machinery is a learned society for computing. It was founded in 1947 as the world's first scientific and educational computing society. Its membership is more than 92,000 as of 2009...
Turing Award
Turing Award
The Turing Award, in full The ACM A.M. Turing Award, is an annual award given by the Association for Computing Machinery to "an individual selected for contributions of a technical nature made to the computing community. The contributions should be of lasting and major technical importance to the...
"in recognition of their seminal paper which established the foundations for the field of computational complexity theory
Computational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
".
Hartmanis was born in Latvia
Latvia
Latvia , officially the Republic of Latvia , is a country in the Baltic region of Northern Europe. It is bordered to the north by Estonia , to the south by Lithuania , to the east by the Russian Federation , to the southeast by Belarus and shares maritime borders to the west with Sweden...
. He was a son of Mārtiņš Hartmanis, a general in the Latvian Army. After the Soviet Union occupied Latvia in 1940
Soviet occupation of Latvia in 1940
The Soviet occupation of Latvia in 1940 refers, according to the European Court of Human Rights, the Government of Latvia, the State Department of the United States of America, and the European Union, to the military occupation of the Republic of Latvia by the Soviet Union ostensibly under the...
, Mārtiņš Hartmanis was arrested by Soviets and died in a prison. At the end of World War II
World War II
World War II, or the Second World War , was a global conflict lasting from 1939 to 1945, involving most of the world's nations—including all of the great powers—eventually forming two opposing military alliances: the Allies and the Axis...
, the wife and children of Mārtiņš Hartmanis left Latvia as refugees, fearing for their safety if the Soviet Union took over Latvia again.
They first moved to Germany
Germany
Germany , officially the Federal Republic of Germany , is a federal parliamentary republic in Europe. The country consists of 16 states while the capital and largest city is Berlin. Germany covers an area of 357,021 km2 and has a largely temperate seasonal climate...
, where Juris Hartmanis received the equivalent of a Bachelor's degree
Bachelor's degree
A bachelor's degree is usually an academic degree awarded for an undergraduate course or major that generally lasts for three or four years, but can range anywhere from two to six years depending on the region of the world...
in Physics from the University of Marburg. Then he moved to the United States
United States
The United States of America is a federal constitutional republic comprising fifty states and a federal district...
, where he received Master's degree
Master's degree
A master's is an academic degree granted to individuals who have undergone study demonstrating a mastery or high-order overview of a specific field of study or area of professional practice...
in Applied Mathematics at the University of Kansas City (now known as the University of Missouri-Kansas City) in 1951 and Ph.D.
Doctor of Philosophy
Doctor of Philosophy, abbreviated as Ph.D., PhD, D.Phil., or DPhil , in English-speaking countries, is a postgraduate academic degree awarded by universities...
in Mathematics from Caltech under the supervision of Robert P. Dilworth
Robert P. Dilworth
Robert Palmer Dilworth was an American mathematician. His primary research area was lattice theory; his biography at the MacTutor History of Mathematics archive states "it would not be an exaggeration to say that he was one of the main factors in the subject moving from being merely a tool of...
in 1955. The University of Missouri-Kansas City honored him with Honorary Doctor of Humane Letters in May 1999.
After teaching at Cornell University
Cornell University
Cornell University is an Ivy League university located in Ithaca, New York, United States. It is a private land-grant university, receiving annual funding from the State of New York for certain educational missions...
and Ohio State University
Ohio State University
The Ohio State University, commonly referred to as Ohio State, is a public research university located in Columbus, Ohio. It was originally founded in 1870 as a land-grant university and is currently the third largest university campus in the United States...
, Hartmanis joined the General Electric
General Electric
General Electric Company , or GE, is an American multinational conglomerate corporation incorporated in Schenectady, New York and headquartered in Fairfield, Connecticut, United States...
Research Laboratory in 1958. While at General Electric, he developed many principles of computational complexity theory. In 1965, he became a professor at Cornell University
Cornell University
Cornell University is an Ivy League university located in Ithaca, New York, United States. It is a private land-grant university, receiving annual funding from the State of New York for certain educational missions...
. At Cornell, he was one of founders and the first chairman of its computer science
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
department (which was one of the first computer science departments in the world). Hartmanis is a Fellow
Fellow
A fellow in the broadest sense is someone who is an equal or a comrade. The term fellow is also used to describe a person, particularly by those in the upper social classes. It is most often used in an academic context: a fellow is often part of an elite group of learned people who are awarded...
of the Association for Computing Machinery
Association for Computing Machinery
The Association for Computing Machinery is a learned society for computing. It was founded in 1947 as the world's first scientific and educational computing society. Its membership is more than 92,000 as of 2009...
and a member of National Academy of Engineering
National Academy of Engineering
The National Academy of Engineering is a government-created non-profit institution in the United States, that was founded in 1964 under the same congressional act that led to the founding of the National Academy of Sciences...
.
He is best known for his Turing-award winning paper with Richard Stearns, in which he introduced time complexity
Time complexity
In computer science, the time complexity of an algorithm quantifies the amount of time taken by an algorithm to run as a function of the size of the input to the problem. The time complexity of an algorithm is commonly expressed using big O notation, which suppresses multiplicative constants and...
classes TIME (f(n))
DTIME
In computational complexity theory, DTIME is the computational resource of computation time for a deterministic Turing machine. It represents the amount of time that a "normal" physical computer would take to solve a certain computational problem using a certain algorithm...
and proved the time hierarchy theorem
Time hierarchy theorem
In computational complexity theory, the time hierarchy theorems are important statements about time-bounded computation on Turing machines. Informally, these theorems say that given more time, a Turing machine can solve more problems...
.