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

INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

En esta clase se encuentra el problema del agente viajero, donde, como ya se mencionó, se quiere
saber si existe una ruta óptima que pasa por todos los nodos requeridos sin repetirlos. Definición:

Un problema de decisión C es NP-Completo si es un problema NP y todo proble-
ma de NP se puede transformar polinomialmente en él. Como consecuencia de
esta definición, si se tuviera un algoritmo polinomial para el problema C, se tendría
una solución en la clase P para todos los problemas de NP.

Esta definición fue propuesta por Stephen Cook en 1971. Cook demostró (teorema de Cook) que
el problema de satisfacibilidad booleana es NP-completo. Desde entonces se ha demostrado que
miles de otros problemas pertenecen a esta clase, casi siempre por reducción a partir de otros pro-
blemas para los que ya se había demostrado su pertenencia a NP-completo.

La teoría de NP-completo no provee algoritmos para resolver los problemas de este grupo en tiempo
polinomial; tampoco dice que no exista algún algoritmo en tiempo polinomial. En lugar de eso, se
explicará que todo aquel problema que no tiene en este momento un algoritmo en tiempo polinomial
está computacionalmente relacionado. En realidad, se pueden establecer dos clases de problemas.
Estos serán los problemas NP-difícil y los NP-completos. Un problema que es NP-completo tendrá
la propiedad de que se puede resolver en tiempo polinomial si y solo si todos los demás NP-com-
pleto también se puede resolver en tiempo polinomial. Si un problema NP-difícil se puede resolver
en tiempo polinomial, entonces todos los problemas NP-completos se pueden resolver en tiempo
polinomial.

Cuando se prueba que un problema de optimización combinatoria en su versión problema de deci-
sión (combinatorio binario) pertenece a la clase NP-completa, entonces la versión de optimización
es NP-difícil.

Mientras que se definen varios problemas con la propiedad de ser clasificados como NP-difícil o
NP-completos (problemas que no se resuelven en forma secuencial en tiempo polinomial), estos
mismos problemas se pueden resolver en máquinas no determinísticas en tiempo polinomial.

algoritmos no determinísticos

Hasta este momento, los algoritmos que se han explicado tienen la propiedad de que el resultado de
toda operación es único y bien definido. Algoritmos con esta propiedad se conocen como algoritmos
determinísticos, los cuales se pueden ejecutar sin problema en una computadora secuencial. En una
computadora teórica, se puede remover esta restricción y permitir operaciones cuya salida no es
única, pero limitada a un conjunto de restricciones. A la máquina que ejecute tales operaciones se
le permitiría escoger alguno de los resultados sujeta a terminar bajo una condición especifica. Esto
conduce al concepto de un algoritmo no determinístico. De esta forma, se definen una nueva función
y dos nuevas declaraciones:

174