El teorema de Cooke-Levin (también solo el teorema de Cooke ) establece que el problema de satisfacibilidad para una fórmula booleana en CNF ( SAT ) es NP-completo .
La demostración de este teorema, obtenida por Stephen Cook en su obra fundamental en 1971 , fue uno de los primeros resultados importantes de la teoría de problemas NP-completos. Independientemente al mismo tiempo, este teorema fue probado por el matemático soviético Leonid Levin [1] .
En la demostración del teorema de Cook, cada problema de la clase NP se reduce explícitamente a SAT. S. Cook definió la clase NP de problemas de reconocimiento de propiedades de la siguiente manera. Una tarea pertenece a la clase NP si:
Esta clase, como mostró más tarde R. Karp, contiene a su vez otra amplia clase de problemas, llamados por Karp problemas NP-completos , o NPC, reducidos unos a otros dentro de esta clase.
Después de la aparición de los resultados de Cook, se demostró la completitud de NP para muchos otros problemas. En este caso, la mayoría de las veces, para probar la completitud NP de un determinado problema, se da una reducción polinomial del problema SAT al problema dado, posiblemente en varios pasos, es decir, utilizando varios problemas intermedios.