Researched
Complexity Theory & NP
Cook and Karp show in 1971/72 that many hard search problems are equally hard; the question 'P versus NP' is born.
Open in the interactive tree →From the 1960s the question was not only whether something is computable but how fast. Stephen Cook proved the first NP-complete problem in 1971, and Richard Karp showed in 1972 that 21 problems, including Hamiltonian cycle and knapsack, are NP-complete. Whether finding is as easy as checking has since mattered for encryption, planning and AI.
Prerequisites
- Graph Theory (Euler)1736Many NP problems (travelling salesman, colouring, cliques) are graph problems
- Boolean Algebra1854Cook's first NP-complete problem is Boolean satisfiability
- Computability (Turing)1936
- Programmable Computer1941
- Linear Optimization (Simplex)1947Karp's NP-complete list includes integer programming, the hard cousin of simplex LP
Unlocks
- P versus NPopen