NP-completitud (teorema de Cook-Levin) y problema P vs NP
NP-completeness (Cook-Levin) and P vs NP
- Fecha
- 1971 · fiabilidad alta
- Lugar
- Toronto, Canadá
- Autoría
- Stephen Cook (1971); Leonid Levin (Moscú, 1973, independiente); 21 problemas NP-completos de Richard Karp (1972)
- Personas
- 👤 Leonid Levin1948–👤 Stephen Cook1939–
- Ámbito
- Saber y símbolos
⚠️ Dato en discusión: las fuentes no coinciden.
Qué se descubrió
La satisfacibilidad booleana es NP-completa: si se resolviera en tiempo polinómico, todo problema cuya solución se verifica rápido también lo sería. Formula la pregunta central de la informática teórica, si P es igual a NP, aún abierta.
Levin obtuvo el resultado independientemente en la URSS con retraso de publicación; Karp mostró en 1972 la ubicuidad de la NP-completitud.
A qué dio paso
- teoría de la complejidad computacional
- criptografía basada en dificultad
- algoritmos de aproximación y heurísticas
- problemas del Milenio
Se apoya en
- Máquina de Turing (concepto de computación universal)1936
- Edmonds (tiempo polinómico, 1965)
- Gödel (carta a von Neumann, 1956)
Hizo posible
- solucionadores SAT industriales
- verificación de hardware