# Juris Hartmanis

> 1928–2022 · Computer Scientist
>
> **Recorded contribution:** Founded computational complexity theory (with Stearns); time hierarchy theorem; Turing Award

## 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

Juris Hartmanis (1928–2022), a Latvian-born computer scientist at Cornell, and Richard Stearns founded computational complexity theory as a systematic study of the resources needed to solve problems. Computability had separated possible from impossible; their 1965 work asked finer questions about how additional time changes what a deterministic Turing machine can decide. The time hierarchy theorem proved that, under suitable constructibility conditions, more time strictly yields more computational power. Hartmanis also helped build Cornell's computer-science department and shared the 1993 Turing Award with Stearns. Complexity classes are mathematical models, and relating them to practical runtime always requires attention to constants, machines, and input distributions.

## 2. The problem inherited

Computability theory classified tasks as decidable or undecidable but said little about why two decidable tasks can demand radically different amounts of computation.

## 3. The central contribution

Hartmanis and Stearns made time and memory explicit complexity measures and proved hierarchy results that separate classes by asymptotic resource bounds.

## 4. Reconstruct the mechanism

1. Choose an abstract machine model and define a function T(n) bounding steps on inputs of length n.
2. Enumerate candidate machines purporting to decide every language within the smaller time bound.
3. Construct a diagonal language that simulates each candidate on its own description and reverses the candidate's answer.
4. Use the larger time allowance to absorb simulation overhead, proving that the diagonal language lies above the smaller class.

## 5. What changed downstream

- Complexity became a distinct discipline concerned with time, space, reductions, completeness, and tradeoffs.
- Hierarchy theorems proved that resource bounds are not merely notation: some problems genuinely require more.
- The framework prepared the ground for P, NP, completeness theory, and modern complexity research.

## 6. Attribution, limits, and uncertainty

- Stearns is an equal co-founder, and the field drew from Rabin, Cobham, Edmonds, and earlier computability work.
- Hierarchy theorems generally separate broad bounds and do not resolve P versus NP.
- Turing-machine asymptotics omit constants, parallel hardware, memory hierarchy, energy, communication, and typical-case structure.

## 7. Reconstruction lab

Implement a bounded universal simulator for several tiny state machines. Define a diagonal language that flips machine i on encoded input i after a step limit, run the first examples, and explain why simulation overhead requires a larger time allowance.

## 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
- [Juris Hartmanis, Founding Chair of Computer Science, Dies at 94](https://news.cornell.edu/stories/2022/08/juris-hartmanis-founding-chair-computer-science-dies-94) — Cornell University

---

*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.*