Page 182 - INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

pias. Si una copia termina en failure, solo ella se detiene. Es importante indicar que una máquina no
determinística no produce ninguna copia de algún algoritmo cada vez que un choice(S) sea ejecuta-
do. Ya que la máquina es ficticia, no es necesario explicar cómo tal máquina determina si existe un
success o un failure. Otra definición de P y NP es esta:

• P es el conjunto de todos los problemas resoluble por un algoritmo determinís-
tico en tiempo polinomial.

• NP es el conjunto de todos los algoritmos de decisión resolubles por un algo-
ritmo no determinístico en tiempo polinomial.

Ya que algoritmos determinísticos son un caso especial de algoritmos no determinísticos, se puede
concluir que P C NP.

Considerando este problema, Cook formuló la siguiente pregunta: ¿hay algún problema en NP único
tal que si se lo mostró estar en P, entonces esto implicaría que P = NP? Cook respondió su propia
pregunta con el siguiente teorema:

Teorema de Cook: satisfacibilidad es en P si y solo si P = NP.

Como paréntesis se puede decir que en teoría de la complejidad computacional, el problema de
satisfacibilidad booleana (también llamado SAT) fue el primero identificado como perteneciente a la
clase de complejidad NP-completo.

Stephen Cook demostró dicha pertenencia en 1971 utilizando una máquina de Turing no determinis-
ta (MTND) a través de la siguiente demostración:

Si se tiene un problema NP, entonces existe una MTND que lo resuelve en tiempo
polinomial conocido p(n). Si se transforma esa máquina en un problema de satisfa-
cibilidad (en un tiempo polinomial n) y se soluciona dicho problema, se habrá obte-
nido también la solución al problema NP original. En tal caso, se habrá demostra-
do que todo problema NP se puede transformar a un problema de satisfacibilidad
y, por lo tanto, el SAT es NP-completo.

176