circagraph
Sign inSign up

The history of computer science

From counting boards and the first algorithms to deep learning: the theory, machines, languages, algorithms, systems, networks, software practice, security and AI that make up computer science, in calendar dates. Moments are tagged and colored by subfield; eras are shown as spans, and links connect ideas to what they led to. Summaries are original; each moment links to its Wikipedia articles as sources. Dates marked approximate say so.

Duration correction: Ongoing subjects previously drawn through a present/research cutoff are represented at their original starts, with no end asserted. Existing moments at those coordinates are reused; their attached cards retain the former duration’s notes, sources, tags and media. Bounded historical and coverage intervals remain durations.

88 moments · 2700-07 BCE – 2022-11-30 CE · by @athan · @athan

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

Sources

Open Computational complexity theory in the timeline

Computational complexity theory · The history of computer…