Teorema de Cook
De Wikipedia, la enciclopedia encyclopedia
En teoría de la complejidad computacional, el Teorema de Cook establece lo siguiente:
|
Cook demostró este teorema en su artículo de 1971 "The Complexity of Theorem Proving Procedures".
El teorema fue demostrado independientemente por Leonid Levin aproximadamente en la misma fecha, por lo que algunas veces es llamado Teorema de Cook-Levin.[1]