The Laureates

Copyright © Klaus Tschira Stiftung / Peter Badge

Richard Edwin Stearns

Born 5 July 1936, Caldwell, New Jersey, USA

ACM A.M. Turing Award (1993) together with Juris Hartmanis “in recognition of their seminal paper which established the foundations for the field of computational complexity theory.”

Richard Edwin Stearns took his bachelor’s degree in Mathematics in 1958 from Carleton College in Northfield, Minnesota. After that he went to Princeton University, located in the State of New Jersey between the cities of New York City and Philadelphia. The topic of his thesis was “Three Person Cooperative Games without Side Payments” (Ph.D. in Mathematics 1961). Stearns then went to the General Electric Research Laboratory in Schenectady, New York State. In 1975 he was Visiting Professor at the Hebrew University in Jerusalem, Israel, and in 1977-1978 Adjunct Professor at Rensselaer Polytechnic Institute in Troy, New York. Stearns left General Electric in 1978 and moved to the State University of New York (SUNY) in Albany. From 1982 to 1989 he was head of the department of Computer Science. In 1985 he was visiting scientist at the Mathematical Sciences Research Institute at the University of California, Berkeley. In 1994, he was honored at the SUNY as a ‘Distinguished Professor’, and has been an emeritus professor since September 2000.

Richard Edwin Stearns was from 1972 to 1988 editor of the Siam Journal of Computing, and from 1973 to 1975 Member-at-Large of the Executive Committee of the ACM Special Interest Group on Algorithms and Computation Theory. He has been a Fellow of ACM since 1994.

With algorithms – that is, computer programs – one can solve maths problems. That takes time. But what does that mean exactly?

The work of Juris Hartmanis and Richard E. Stearns deals with precisely this question: how to measure the complexity of problems and the time required by the algorithms for their solution. In 1964 the two men proposed in ‘Computational Complexity of Recursive Sequences’ a way to estimate the complexity of a problem by the speed of an algorithm that solves that problem.

For measuring the speed, they used Turing machines, a formalism used to describe computer algorithms in a standardised way, which is named after the British mathematician Alan Turing. Hartmanis and Stearns took the number of calculations that the algorithm would need on a Turing machine as a measure of time. This resulted in a new class of problems: DTIME(f). In this class are all problems that need no more time than f(n) for their solution with the Turing machine, where f(n) is a function that grows with the size of the problems – measured in terms of n. Hartmanis and Stearns later extended this model by integrating the memory necessary to solve the problems.