Stephen Cook
Stephen Cook es un Matemáticas|matemático y científico de la computación canadiense-estadounidense nacido el 14 de diciembre de 1939 en Buffalo, Nueva York. Se graduó en Matemáticas en la Universidad de Michigan en 1961 y obtuvo su doctorado en Matemáticas en la Universidad de Harvard en 1966. Su interés por la teoría de la computación lo llevó a trabajar como profesor en la Universidad de California, Berkeley, antes de unirse a la Universidad de Toronto en 1970, donde desarrolló gran parte de su trabajo seminal.
En 1971, publicó el influyente artículo "The Complexity of Theorem-Proving Procedures", donde introdujo el concepto de problemas NP-completos y demostró que el problema de satisfacibilidad booleana (SAT) es NP-completo. Este resultado, conocido como el Teorema de Cook, marcó un hito en la historia de la computación y sentó las bases para el estudio moderno de la teoría de la complejidad.
NP-completitud y el Teorema de Cook
El teorema establece que: 1. SAT es un problema que pertenece a la clase NP, es decir, sus soluciones pueden ser verificadas en tiempo polinomial. 2. SAT es NP-completo, lo que significa que cualquier problema en NP puede ser reducido a SAT en tiempo polinomial.
Esto implica que resolver SAT de manera eficiente permitiría resolver cualquier problema NP en tiempo polinomial. Esta conexión entre los problemas NP-completos es fundamental para entender por qué algunos problemas son intrínsecamente difíciles de resolver.
Contribuciones clave
1. Definición de NP-completitud:
Cook formalizó el concepto de problemas NP-completos, que son aquellos que: - Pertenecen a NP. - Son al menos tan difíciles como cualquier otro problema en NP.
2. Impacto en la computación:
La clasificación de un problema como NP-completo no solo ayuda a comprender su complejidad, sino que también motiva la búsqueda de algoritmos aproximados o heurísticos cuando no es posible resolverlos exactamente.
3. Fundamento de P vs NP:
El trabajo de Cook plantea la pregunta central de la teoría de la complejidad: ¿P es igual a NP?. Este problema sigue siendo uno de los mayores desafíos en matemáticas y computación.