Background
Hartmanis, Juris was born on July 5, 1928 in Riga, Latvia. Son of Martins and Irma (Liepins) Hartmanis. came to the United States, 1950, naturalized, 1956.
(An overview of current developments in research on feasib...)
An overview of current developments in research on feasible computations; and a consideration of this area of research in relation to provable properties of complexity of computations. The author begins by defining and discussing efficient reductions between problems and considers the families and corresponding complete languages of NL, DCSL, CSL, P, NP, PTAPE, EXPTIME, and EXPTAPE. Definitions and results are uniformly extended to computationally simpler natural families of languages such as NL, P, and CSL by using Log n-tape bounded reductions. The problem of determining what can and cannot be formally proven about running times of algorithms is discussed and related to the problem of establishing sharp time bounds for one-tape Turing machine computations, and the inability to formally prove running times for algorithms is then related to the presence of gaps in the hierarchy of complexity classes.
http://www.amazon.com/gp/product/0898710278/?tag=prabook0b-20
mathematician university professor computer scientist
Hartmanis, Juris was born on July 5, 1928 in Riga, Latvia. Son of Martins and Irma (Liepins) Hartmanis. came to the United States, 1950, naturalized, 1956.
Student, University Marburg, 1949. Master of Arts, University Kansas City, 1951. Doctor of Philosophy, California Institute of Technology, Pasadena, 1955.
Doctor of Humane Letters (honorary), University Dortmund, Germany, 1995. Doctor (honorary), University Missouri, 1999. Doctor of Humane Letters (honorary), University Missouri, 1999.
After the Soviet Union occupied Latvia in 1940, Mārtiņš Hartmanis was arrested by Soviets and died in a prison. They first moved to Germany, where Juris Hartmanis received the equivalent of a Master"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 Doctor of Philosophy 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).
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.
Another paper by Hartmanis from 1977, with Leonard Berman, introduced the still-unsolved Berman–Hartmanis conjecture that all Natural Philosophy-complete languages are polynomial time isomorphic.
(An overview of current developments in research on feasib...)
Fellow: American Association for the Advancement of Science, Computing Machinery, American Academy Arts and Sciences. Member: National Academy of Engineering, Latvian Academy of Sciences (foreign, Grand medal 2001), Association New York Academy of Sciences, American Mathematics Society, Sigma Xi.
Married Ellymaria Rehwald, May 16, 1959. Children: Reneta, Martin, Audrey.