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

INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

En este momento se puede definir mejor los tipos de problemas NP-difíciles y NP-completo. Primero
se definirá la noción de reducibilidad. Definición: Sean L y L dos problemas. L reduce a L (L a L )
1 2 1 2 1 2
si y solo si existe un camino para resolver L con un algoritmo polinomial determinístico también se
1
usará un algoritmo determinístico de tiempo polinomial que resuelva a L .
2
Esta definición implica que si existe un algoritmo determinístico en tiempo polinomial para L , enton-
2
ces podemos resolver L en tiempo polinomial. Este operador es transitivo, esto es, si L є L y L є
1 1 2 2
L entonces L a L .
3 1 3
Un problema cualquiera (de función o de decisión) es NP-difícil si y solo si todo problema en NP
es reducible a . Y si además de ser NP-difícil, está en NP (es problema de decisión), decimos
que es un problema NP-completo. El diagrama de Venn que se muestra en la figura 8.2 aclara la
relación de estas clases.

Figura 8.2. Diagrama de Venn que muestra la relación P y NP

Un problema NP-difícil puede no ser NP-completo. Solo un problema de decisión puede ser NP-com-
pleto. Sin embargo, un problema de optimización puede ser NP-difícil. Además, si L es un problema
1
de decisión y L es un problema de optimización, es bastante posible que L a L . Se puede observar
2 1 2
que el problema de decisión de la mochila se puede reducir al problema de optimización de la mochi-
la. También se puede comentar que el problema de optimización se puede reducir a su correspon-
diente problema de decisión. Por lo tanto, problemas de optimización no pueden ser NP-completos,
mientras que algunos problemas de decisión pueden ser del tipo NP-duro y no son NP-completos.

178