01 · A life in computing
The person behind the work
Juris Hartmanis helped found computational complexity theory by asking how time and memory limit what algorithms can accomplish. With Richard Stearns at General Electric, he developed a framework for classifying problems by computational resources and proving hierarchy results. He later built Cornell’s computer science department. His work shifted attention from whether a problem is computable to how much computation its solution requires.
The contribution, explained
Juris Hartmanis and Richard Stearns established foundations for computational complexity theory. Instead of asking only whether a problem is computable, they examined the resources required as inputs grow. Their work helped show that allowing more computational time can genuinely increase what a machine can do.
Why it matters
Resource-based classes gave computer science a language for comparing problems and understanding computational limits.