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
- P versus NP on The history of mathematics by @athan