Juris Hartmanis

Juris Hartmanis (1928 to 2022) was a Latvian-born American computer scientist and mathematician who, together with Richard E. Stearns, founded the field of computational complexity theory. Born in Latvia, he left as a refugee in 1944, studied physics in Marburg, took a master's degree in applied mathematics at the University of Kansas City in 1951 and a Ph.D. in mathematics at Caltech in 1955 under Robert P. Dilworth. After teaching at Cornell and Ohio State he joined the General Electric Research Laboratory in 1958, where he developed many principles of complexity theory, and in 1965 he became a professor at Cornell and the first chair of its computer science department. Their 1965 paper defined complexity classes and led to results such as the time hierarchy theorem, and with P. M. Lewis II they proved the first space hierarchy theorem. He also proved with Leonard Berman that natural NP-complete languages are polynomial-time isomorphic. Hartmanis and Stearns shared the 1993 ACM Turing Award; he was a member of the National Academy of Engineering and the National Academy of Sciences, and was assistant director of the National Science Foundation computing directorate from 1996 to 1998.