Computational complexity theory
- theory
Juris Hartmanis and Richard Stearns’s 1965 paper examined how much computation an algorithm requires as its input grows. By organizing problems according to resource bounds, their work helped establish computational complexity as a systematic mathematical field. The question differs from computability: a problem can have an algorithm yet demand impractical amounts of time or memory. Abstract machine models allow researchers to compare growth rates and prove relationships between classes of problems. The paper is a foundational milestone within a wider history, rather than the first occasion on which anyone noticed that some computations take longer than others. **Timeline anchor:** 1 January 1965 CE. **References:** [Source 1](https://en.wikipedia.org/wiki/Computational_complexity_theory).