Richard E Stearns

The A.M. Turing Award is presented to Juris Hartmanis and Richard E. Stearns in recognition of their seminal joint research which established the foundations for the field of computational complexity theory. In their paper On the Computational Complexity of Algorithms (Transactions of the American Mathematical Society, vol. 117, No. 5, May 1965, pp. 285-306) they provided a precise definition of the complexity measure defined by computation time on Turing machines and developed a theory of complexity classes. The paper sparked the imagination of many computer scientists and led to the establishment of complexity theory as a fundamental part of the discipline.