NP-completeness (Cook-Levin) and P vs NP
NP-completitud (teorema de Cook-Levin) y problema P vs NP
- Date
- 1971 · confidence high
- Place
- Toronto, Canada
- Credited to
- Stephen Cook (1971); Leonid Levin (Moscow, 1973, independent); Richard Karp's 21 NP-complete problems (1972)
- People
- 👤 Leonid Levin1948–👤 Stephen Cook1939–
- Field
- Knowledge & symbols
⚠️ Disputed: the sources disagree.
What was discovered
Boolean satisfiability is NP-complete: if it were solved in polynomial time, every problem whose solution can be verified quickly would be too. It formulates the central question of theoretical computer science, whether P equals NP, still open.
Levin obtained the result independently in the USSR, with delayed publication; Karp showed in 1972 how ubiquitous NP-completeness is.
What it led to
- computational complexity theory
- hardness-based cryptography
- approximation algorithms and heuristics
- the Millennium Problems
Built on
- Turing machine (universal computation)1936
- Edmonds (polynomial time, 1965)
- Gödel (letter to von Neumann, 1956)
Made possible
- industrial SAT solvers
- hardware verification