Tugurium/GTI

Glosario Terminología Informática

Cook, Stephen Arthur

0 Estados Unidos, 1939 -
Formalizó la noción NP-completo en 1971 en el artículo "The Complexity of Theorem Proving Procedures" (La complejidad de los procedimientos de prueba de teoremas), donde enuncia el Teorema de Cook, una prueba de que el problema de satisfacibilidad booleana es NP-completo. El artículo deja sin resolver la pregunta abierta más grande de la informática teórica, si las clases complejas P y NP son equivalentes.
2005-12-14
Stephen A. Cook

Stephen A. Cook