# Richard Stearns

> 1936–2023 · Computer Scientist
>
> **Recorded contribution:** Founded computational complexity theory (with Hartmanis); time hierarchy theorem

## How to use this dossier

Read for a causal chain, not a hero story: inherited problem → contribution → mechanism → downstream capability → limit. Then close the page and complete the reconstruction exercise from memory.

## 1. Historical orientation

Richard Stearns (1936–2023) co-founded computational complexity theory with Juris Hartmanis. Their 1965 paper formally treated the time needed by a multitape Turing machine as a property for classifying problems and proved that additional constructible time creates strictly larger language classes. Stearns later contributed to automata and game theory and shared the 1993 Turing Award with Hartmanis. The hierarchy result was a conceptual shift from 'can a machine compute this?' to 'how much resource must computation consume?' It does not resolve P versus NP, but it proves that some resource distinctions are mathematically real.

## 2. The problem inherited

Computability's yes/no boundary grouped trivial and astronomically expensive algorithms together, leaving no formal vocabulary for feasible versus resource-intensive computation.

## 3. The central contribution

Stearns and Hartmanis defined machine time complexity and used diagonal simulation to prove a deterministic time hierarchy.

## 4. Reconstruct the mechanism

1. Fix an encoding of machines and a time-constructible upper bound that a simulator can track.
2. Enumerate machines operating within a smaller time allowance and simulate the indexed machine on its encoded self-input.
3. Reverse that machine's answer when the bounded simulation halts, ensuring disagreement with every smaller-bound decider.
4. Use the larger resource bound to pay simulation overhead and decide the constructed language.

## 5. What changed downstream

- Time and space complexity became formal objects independent of particular program text.
- Hierarchy arguments became reusable tools throughout complexity theory.
- The work prepared the conceptual ground for completeness, reductions, and tractability research.

## 6. Attribution, limits, and uncertainty

- Hartmanis shares the founding work, which also built on Rabin, Cobham, and computability theory.
- The theorem separates suitable asymptotic bounds but does not identify a natural problem separating P and NP.
- Abstract step counts omit constants, architectures, parallelism, data movement, and energy.

## 7. Reconstruction lab

Construct a table of five tiny deciders and define a bounded diagonal language that disagrees with row i on input i. Implement the table, then explain how encoding and simulation overhead alter the required larger bound.

## 8. Evidence trail

- [On the Computational Complexity of Algorithms](https://doi.org/10.1090/S0002-9947-1965-0170805-7) — Transactions of the American Mathematical Society
- [Richard Edwin Stearns](https://en.wikipedia.org/wiki/Richard_Stearns_(computer_scientist)) — Wikimedia Foundation

---

*Research checked 2026-08-09. Dates, roles, and claims about living people are historical snapshots. Linked sources remain the authority; this dossier is original instructional synthesis.*