---
title: On the Computational Complexity of Algorithms
authors:
  - J. Hartmanis
  - R. E. Stearns
year: 1965
venue: Transactions of the AMS
arxiv: null
doi: 10.1090/S0002-9947-1965-0170805-7
source: "https://doi.org/10.1090/S0002-9947-1965-0170805-7"
topics:
  - complexity
  - hartmanis-stearns
seed_rank: 728
seed_batch: perfects-algorithms-2026-08-13
reviewed: 2026-08-13
pool: maths-foundations
relevance_score: 9
lineage: algorithms-and-complexity
cites: []
see: []
---

# On the Computational Complexity of Algorithms

## One-sentence takeaway

Time-bounded multi-tape Turing machines become a mathematical object: complexity classes, speed-up, and hierarchy theorems, not just decidability.

## Why it matters here

This is the paper that makes “how much time?” a theorem, not a stopwatch. Every later Anoptic discussion of P, NP, or space bounds inherits Hartmanis–Stearns’s decision to treat resource-bounded computation as the subject.

## Key ideas

- Multi-tape Turing machines with an explicit time bound define complexity classes as sets of languages.
- Speed-up and hierarchy phenomena show that more time buys more languages, with quantitative gaps.
- The work shifts attention from computability (can it halt?) to resource-bounded computation (can it halt in \(T(n)\)?).
- Blum’s later axiomatic theory and Savitch’s space simulation sit downstream of this founding paper.
- Trans. Amer. Math. Soc. 117, 1965, pp. 285–306.

## Caveats

## Links

- DOI: [10.1090/S0002-9947-1965-0170805-7](https://doi.org/10.1090/S0002-9947-1965-0170805-7)
- AMS: https://www.ams.org/journals/tran/1965-117-00/S0002-9947-1965-0170805-7/