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

INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

Estos problemas de decisión en los que la solución parece difícil, pero verificarla parece sencillo,
forman su propia clase de complejidad, conocida como NP. Se ha dicho parecen, porque, como se
ha comentado, no se sabe hoy en día si realmente son tan difíciles de resolver.

Como primera observación, se recalcará que en NP solo hay problemas de decisión. Así, en NP está
la versión de decisión de TSP, pero no el problema de función más general de encontrar la ruta ópti-
ma. La segunda observación es que la búsqueda del certificado es un algoritmo. No el algoritmo que
resuelve el problema, sino el que lo verifica. Finalmente, es importante hacer notar que el tiempo para
dar por bueno el certificado, el tiempo de ejecución de este algoritmo, es polinómico con respecto a
la cadena de entrada. Pero ¿cuál sería un posible certificado para TSP como problema de decisión?
Claramente, el camino hamiltoniano.

Cook afirma que es trivial mostrar que P C NP y también afirma que hay dos formas de establecer si
un problema pertenece a la clase NP:

• Si su solución implica el uso de una máquina de Turing no determinística en
tiempo polinomial,

• o si su solución se puede verificar en una máquina de Turing determinística en
tiempo polinomial.

Es posible demostrar que un problema pertenece a la clase P mediante dos formas:

• mostrando un algoritmo polinomial que lo resuelve,

• o usando una transformación polinomial a otro problema que ya se sabe que
está en la clase P.

Una transformación polinomial de B en C es un algoritmo determinista que transforma instancias de
b B en instancias de c C, tales que la respuesta a c es positiva si y solo si la respuesta a b lo es.

P puede ser un subconjunto propio de NP o P puede ser igual a NP. Es algo que no se sabe. De
hecho, es el problema abierto más importante de la teoría de la complejidad computacional y uno de
los más importantes de la matemática:
¿P = NP? o ¿P ≠ NP?

La inmensa mayoría de los expertos piensa que P ≠ NP, aunque no se ha podido demostrar. La im-
portancia de la clase de problemas NP es que contiene muchos problemas de búsqueda y de opti-
mización para los que se desea saber si existe cierta solución o si hay una mejor que las conocidas.

173