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

NP-completeness (Cook–Levin)

  • theory

Stephen Cook’s 1971 work established the NP-completeness of Boolean satisfiability; Leonid Levin independently developed closely related ideas. NP concerns problems whose proposed solutions can be verified within polynomial time, while a complete problem can represent the difficulty of every problem in that class through suitable reductions. The result gave researchers a way to connect many apparently different search and decision problems. A polynomial-time algorithm for any NP-complete problem would imply P equals NP. The theorem did not prove that such an algorithm is impossible, and the broader P-versus-NP question remains distinct from demonstrating one problem’s completeness. **Timeline anchor:** 1 May 1971 CE. Approximate day. **References:** [Source 1](https://en.wikipedia.org/wiki/Cook%E2%80%93Levin_theorem), [Source 2](https://en.wikipedia.org/wiki/P_versus_NP_problem).

Sources

On other timelines

Open NP-completeness (Cook–Levin) in the timeline

NP-completeness (Cook–Levin) · The history of computer…