Juris Hartmanis

Juris Hartmanis (July 5, 1928 – July 29, 2022) was a Latvian-born American 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".

Life and career

Hartmanis was born in Latvia on July 5, 1928.<ref>Template:Cite book</ref> He was a son of Template:Interlanguage link,<ref>In the Baltic languages, own-names are not lexical constants, but have different grammatical forms. Hartmanis must be understood as Hartman-is, whereby Hartman is the stem of the own-name, whereas the suffix -is indicates a masculine grammatical form in the Latvian language. In a similar manner, for example, the philosopher Kant is known as Kantas in the Lithuanian language.</ref> a general in the Latvian Army, and Irma Marija Hartmane. He was the younger brother of the poet Astrid Ivask. After the Soviet Union occupied Latvia in 1940, Mārtiņš Hartmanis was arrested by the Soviets and died in prison. Later in World War II, the wife and children of Mārtiņš Hartmanis left Latvia in 1944 as refugees, fearing for their safety if the Soviet Union took over Latvia again.Template:Refn<ref name="Tribute to his sister">Template:Cite web</ref>

They first moved to Germany, where Juris Hartmanis received the equivalent of a master's degree in physics from the University of Marburg. He then moved to the United States, where in 1951 he received a master's degree in applied mathematics at the University of Kansas City (now known as the University of Missouri–Kansas City) and in 1955 a Ph.D. in mathematics from Caltech under the supervision of Robert P. Dilworth.<ref name="JurisThesis">Template:Cite thesis</ref> The University of Missouri–Kansas City honored him with an Honorary Doctor of Humane Letters in May 1999.<ref name="MissouriHonorary" /> After teaching mathematics 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.Template:Refn In 1965, he became a professor at Cornell University. He was one of the founders and the first chair of its computer science department (which was one of the first computer science departments in the world).Template:Refn

Hartmanis contributed to national efforts to advance computer science and engineering (CS&E) in many ways. Most significantly, he chaired the National Research Council study that resulted in the 1992 publication Computing the Future – A Broad Agenda for Computer Science and Engineering,<ref name="ComputingTheFuture">Template:Cite book</ref> which made recommendations based on its priorities to sustain the core effort in CS&E, to broaden the field, and to improve undergrad education in CS&E. He was assistant director of the National Science Foundation (NSF) Directorate of Computer and Information Science and Engineering (CISE)<ref>Template:Cite web</ref> from 1996 to 1998.

In 1989, Hartmanis was elected as a member into the National Academy of Engineering for fundamental contributions to computational complexity theory and to research and education in computing. He was a Fellow of the Association for Computing Machinery and of the American Mathematical Society,<ref name="auto">List of Fellows of the American Mathematical Society, retrieved January 19, 2013.</ref> also a member of the National Academy of Sciences.<ref name="NASmember">National Academy of Sciences Members and Foreign Associates Elected Template:Webarchive, National Academy of Sciences, April 30, 2013.</ref> He was also a foreign member of the Latvian Academy of Sciences,<ref name=LZA /> which bestowed him their Template:Ill in 2001 for his contributions to computer science.<ref name=LZAGrandMedal />

Hartmanis died on July 29, 2022.<ref name="XinZhiYuan (Chinese obituary)">Template:Cite web</ref><ref name="Cornell-Obit">Template:Cite web</ref><ref name="CACMObit">Template:Cite journal</ref>

Computational complexity: foundational contributions

In 1993, Hartmanis and R.E. Stearns received the highest prize in computer science, the Turing Award. The citation reads, "In recognition of their seminal paper which established the foundations for the field of computational complexity theory."<ref name="ACMTuringAward" /> Their paper<ref name="TuringPaper" /> defined the foundational notion of a Complexity class, a way of classifying computational problems according to the time required to solve them. They went on to prove a number of fundamental results such as the Time hierarchy theorem. In his own Turing Award lecture, Richard M. Karp remarks that "[I]t is the 1965 paper by Juris Hartmanis and Richard Stearns that marks the beginning of the modern era of complexity theory."Template:Refn

With P.M. Lewis II, Hartmanis and Stearns also defined complexity classes based on space usage. They proveded the first space hierarchy theorem.<ref name="MemoryLimitedComps" /> In the same year they also proved<ref name="MemoryBoundsForRecognition" /> that every context-free language has deterministic space complexity Template:Math, which contained the essential idea that led to Savitch's theorem on space complexity.

Hartmanis continued to make significant contributions to the field of computational complexity for decades. With Leonard Berman, he proved that all natural NP-complete languages are polynomial-time isomorphic<ref name="HartManisBerman" /> and conjectured that this holds for all NP-complete sets.Template:Refn Although the conjecture itself remains open, it has led to a large body of research on the structure of NP-complete sets, culminating in Mahaney's theorem on the nonexistence of sparse NP-complete sets.<ref>Template:Cite journal</ref><ref name="CaiSivakumar">Template:Citation</ref>Template:RefnTemplate:Refn He and his coauthors also defined the Boolean hierarchy.<ref name="boolHierarchy1">Template:Citation</ref><ref name="boolHierarchy2">Template:Citation</ref>

Hartmanis's 1981 article <ref name="Observations1981">Template:Citation</ref> gives a personal account of developments in this area and in automata theory and discusses the underlying beliefs and philosophy that guided his research. The book written in honor of his 60th birthday,<ref name="ComplexityRetrospective">Template:Cite book</ref> in particular, the chapter by Stearns,<ref>Template:Cite book</ref> is a valuable resource on computational complexity.

In the late 1980s, Hartmanis's exposition<ref name="MisfiledLetter" /> on a newly discovered letter dated 20 March 1956 from Gödel to von Neumann brought fresh insight into the early history of computational complexity before his landmark paper with Stearns, touching on interactions among Turing, Gödel, Church, Post, and Kleene. Gödel, in this letter, was the first to question whether a problem equivalent to an NP-complete problem could be solved in quadratic or linear time, presaging the P = NP? question.

Awards

• Fellow, American Association for the Advancement of Science (AAAS),<ref>Template:Cite web</ref> 1981
• Member, National Academy of Engineering,<ref>Template:Cite web</ref> 1989
• Member (foreign): Latvian Academy of Sciences,<ref name=LZA>Template:Cite web</ref> 1990
• Member, American Academy of Arts and Sciences,<ref>Template:Cite web</ref> 1992
• ACM Turing Award<ref name="ACMTuringAward">Template:Cite web</ref> 1993
• Humboldt Foundation Research Award,<ref>Template:Cite web</ref> 1993
• Charter Fellow, ACM,<ref>Template:Cite web</ref><ref>Template:Cite web</ref> 1994
• Honorary Doctor of Humane Letters,<ref name="MissouriHonorary" /> 1999
• Computing Research Association (CRA) Distinguished Service Award,<ref name="CRA">Template:Cite web</ref> 2000
• Template:Ill of the Latvian Academy of Sciences, 2001<ref name=LZAGrandMedal>Template:Cite web</ref>
• ACM Distinguished Service Award,<ref>Template:Cite web</ref><ref>Template:Cite web</ref> 2013
• Inaugural Fellow, American Mathematical Society,<ref name="auto"/> 2013
• Member, National Academy of Sciences,<ref name="NAS">Template:Cite web</ref> 2013

Selected publications

Books

• Algebraic Structure Theory of Sequential Machines<ref name="AlgebraicStructure">Template:Cite book</ref> 1966 (with R.E. Stearns)
• Feasible Computations and Provable Complexity Properties<ref name="FeasibleComputations">Template:Cite book</ref> 1978
• Computational Complexity Theory (ed.)<ref name="CompComplexityTheory">Template:Cite book</ref> 1989
• Computing the Future: A broader agenda for computer science and engineering (ed.)<ref name="ComputingFuture">Template:Cite book</ref> 1992 (with Herbert Lin)

Selected articles

• "Computational complexity of recursive sequences"<ref name="RecursiveSequences" /> 1964 (with R.E. Stearns)
• "Classifications of computations by time and memory requirements"<ref name="TimeMemory" /> 1965 (with P.M. Lewis and R.E. Stearns)
• "Hierarchies of memory limited computations"<ref name="MemoryLimitedComps" /> 1965 (with P.M. Lewis and R.E. Stearns)
• "On the computational complexity of algorithms"<ref name="TuringPaper" /> 1965 (with R.E. Stearns)
• Memory bounds for recognition of context-free and context-sensitive languages<ref name="MemoryBoundsForRecognition" /> 1965 (with P.M. Lewis and R.E. Stearns)
• "On isomorphisms and density of NP and other complete sets"<ref name="HartManisBerman" /> 1977 (with L. Berman)
• "Observations about the development of theoretical computer science"<ref name="Observations1981" /> 1981
• "Gödel, von Neumann, and the P =? NP problem"<ref name="MisfiledLetter" /> 1989

Interviews

Juris Hartmanis has been interviewed four times. Videos are available for two of them. The most far-reaching one is by William Aspray.

• William Aspray interviews Hartmanis for the ACM Oral History interviews,<ref name="JHAsprayInterview" /> 2009
• David Gries interviews Hartmanis for the Cornell ecommons collection,<ref name="JHEcommonsInterview">Template:Cite interview</ref> 2010
• Len Shustek interviews Hartmanis in an article in Communications of the ACM,<ref name="JHCACMInterview">Template:Cite journal</ref> 2015
• David Gries interviews Hartmanis as ACM Turing Award recipient,<ref name="JHTuringInterview" /> 2018

External links

• Hartmanis biography at A.M. TURING AWARD, Short Annotated Bibliography
• Hartmanis biography at Cornell
• Template:MathGenealogy