World Library  
Flag as Inappropriate
Email this Article

Juris Hartmanis

Article Id: WHEBN0000305842
Reproduction Date:

Title: Juris Hartmanis  
Author: World Heritage Encyclopedia
Language: English
Subject: List of Turing Award laureates by university affiliation, Turing Award, Dexter Kozen, Robert P. Dilworth, Asymptotic computational complexity
Collection: 1928 Births, California Institute of Technology Alumni, Cornell University Faculty, Fellows of the American Mathematical Society, Fellows of the Association for Computing MacHinery, Latvian Computer Scientists, Latvian Emigrants to the United States, Living People, Members of the United States National Academy of Engineering, Members of the United States National Academy of Sciences, People from Riga, Theoretical Computer Scientists, Turing Award Laureates
Publisher: World Heritage Encyclopedia

Juris Hartmanis

Juris Hartmanis
Born (1928-07-05) July 5, 1928
Riga, Latvia
Fields Computer Science
Institutions General Electric
Cornell University
Alma mater California Institute of Technology
Doctoral students Allan Borodin
Dexter Kozen
Janos Simon
Notable awards Turing Award (1993)

Juris Hartmanis (born July 5, 1928) 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 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 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 of the American Mathematical Society[1] and a member of the National Academy of Engineering and National Academy of Sciences.[2]

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 NP-complete languages are polynomial time isomorphic.

Selected publications

  • Berman, L.; Hartmanis, J. (1977), "On isomorphisms and density of NP and other complete sets", SIAM Journal on Computing 6 (2): 305–322, .  
  • Hartmanis, J.;  .


  1. ^ List of Fellows of the American Mathematical Society, retrieved 2013-01-19.
  2. ^ National Academy of Sciences Members and Foreign Associates Elected, National Academy of Sciences, April 30, 2013.

External links

This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.

Copyright © World Library Foundation. All rights reserved. eBooks from Project Gutenberg are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.