Teorema de Cook

En teoría de la complejidad computacional, el Teorema de Cook establece lo siguiente:

El Problema de satisfacibilidad booleana (SAT) es NP-completo.


Stephen Cook (1971)

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]

Definiciones

Un problema de decisión pertenece a NP si puede ser resuelto en una Máquina de Turing indeterminista en tiempo polinómico.

Se dice que un problema de decisión es NP-completo si pertenece a NP y si todo problema perteneciente a NP puede ser reducido a él utilizando una transformación polinómica.

Una instancia del problema SAT es una expresión booleana que combina variables booleanas con operadores booleanos. Una expresión es satisfacible si existe una asignación de valores booleanos para las variables de esa expresión que hace que la expresión completa sea verdadera.

Other Languages
Deutsch: Satz von Cook
Bahasa Indonesia: Teorema Cook
srpskohrvatski / српскохрватски: Cook-Levinov teorem
Simple English: Cook–Levin theorem