+- MKLab (https://mklab.gr)
+-- Forum: [INDEX] (https://mklab.gr/forumdisplay.php?fid=1)
+--- Forum: MATHEMATICS (https://mklab.gr/forumdisplay.php?fid=3)
+---- Forum: ARTICLES (https://mklab.gr/forumdisplay.php?fid=13)
+----- Forum: HISTORY (https://mklab.gr/forumdisplay.php?fid=152)
+----- Thread: Richard Stearns (1936-2026) (/showthread.php?tid=1891)
Richard Stearns (1936-2026) - mklabgr - 09-07-2026
Authors: Eugene H. Spafford and Simson L. Garfinkel
Published: September 3, 2026, Communications of the ACM
Area: Theoretical Computer Science — Computational Complexity Theory
The article commemorates Richard E. Stearns (1936–2026), one of the founders of modern computational complexity theory. His most influential contribution came through his 1965 paper with Juris Hartmanis, On the Computational Complexity of Algorithms. That work introduced a rigorous way of classifying computational problems according to the resources—especially time—required to solve them, developing notions such as $DTIME(T(n))$. It also established early time-hierarchy results, showing in a precise mathematical sense that giving a machine more computational time can allow it to solve strictly more problems. This conceptual framework helped transform questions about whether algorithms merely existed into questions about how efficiently computation could actually be performed. Stearns and Hartmanis received the 1993 ACM A.M. Turing Award for this foundational work.
Stearns' influence extended well beyond complexity theory. His research covered automata and formal-language theory, compiler construction, algorithm analysis, databases, and game theory. Among his important results were work on deterministic pushdown automata and, with Philip Lewis, research that helped introduce LL parsing, which became important in compiler design. He spent 17 years at General Electric Research Laboratory before joining the University at Albany, where he spent more than two decades and served as department chair. Even late in his career, he continued publishing research, illustrating an unusually long scientific life. Stearns died on August 29, 2026, at age 90, leaving behind concepts that are now part of the basic language of theoretical computer science.
Key takeaways
- Stearns was a father of computational complexity theory, helping formalize the study of computational resources.
- The 1965 Hartmanis–Stearns paper provided foundations for complexity classes such as $DTIME(T(n))$ and the time hierarchy theorem.
- His contributions also reached formal languages, parsing and compilers, databases, algorithms, and game theory.
- His work helped establish one of computer science's central questions: not simply “Can a problem be solved?”, but “How much computational time or other resources are fundamentally required to solve it?”
ARTICLE