P versus NP
- computation
- american
Stephen Cook’s 1971 theorem made Boolean satisfiability a complete problem for NP, a class characterized by polynomial-time verification of proposed solutions. Reductions connect its difficulty to that of every problem in the class. This gave a precise framework for studying the gap between efficiently finding a solution and efficiently checking one. Whether P equals NP remains a separate question; NP-completeness does not itself prove that efficient algorithms are impossible. The milestone helped organize mathematical complexity and practical discussions of difficult search and optimization problems. **Timeline anchor:** 1 January 1971 CE. **References:** [Source 1](https://en.wikipedia.org/wiki/P_versus_NP_problem).
Sources
On other timelines
- NP-completeness (Cook–Levin) on The history of computer science by @athan