1993 · Theory & algorithms
Complexity theory studies the time and memory needed to solve problems.
Visual guide
Choose time or memory as a resource.
Group problems by their needs.
Study what extra resources enable.
Resource-based classes gave computer science a language for comparing problems and understanding computational limits.
Complexity classes describe mathematical models and growing input families, not a stopwatch measurement on one machine.
01 · The idea
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.
Resource-based classes gave computer science a language for comparing problems and understanding computational limits.
02 · The people
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.
Read the biography ↗
Richard Stearns co-developed the foundations of computational complexity theory with Juris Hartmanis while working at General Electric. Their research made time and space explicit mathematical resources for classifying computational problems. Stearns also worked on automata, algorithms, and game theory. He later taught at the University at Albany, where he helped build computer science research and education and served as department chair.
Read the biography ↗03 · Read further
Original explanations based on the official award record. The subject label is an editorial navigation aid.
Complexity theory connected random choices with some of computation’s deepest limits.
The story
Numerical libraries connect mathematical algorithms with changing hardware.
The story