Page 185 - INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS
P. 185
INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS
ejemplo de un problema de decisión Np-difícil (Np-hard)
Considere el problema del paro para un algoritmo determinístico. El problema del paro (the halting
problem) es determinar para un arbitrario algoritmo determinístico A y una entrada I si el algoritmo
A con la entrada I termina (o entra en un ciclo infinito). Este problema es indecidible, por lo que no
existe algoritmo (de ninguna complejidad) para resolver este problema. Es decir, el problema no es
del tipo NP. Para poder mostrar satisfacibilidad a halting problem, simplemente se construye un
algoritmo A cuya entrada es una formula proposicional X. Si X tiene n variables, entonces A realiza
los 2 posibles asignaciones y verifica si X es satisfacible. Si lo es, entonces A se detiene. Si X no es
n
satisfacible, entonces A entra en un ciclo infinito. Si tenemos un algoritmo en tiempo polinomial para
el halting problem entonces podemos resolver el problema de la satisfacibilidad en tiempo polinomial
usando A y X como entrada del algoritmo para the halting problem. Por ello, el problema del paro es
NP-difícil, pero no está en NP.
Definición. Dos problemas L y L son polinomialmente equivalentes si y solo si L a L y L a L .
1 2 1 2 2 1
Para mostrar que un problema, L , es NP-difícil es adecuado mostrar que L a L , donde L es algún
2 1 2 1
problema ya conocido como NP-difícil. Ya que a es un operador transitivo, se muestra que si satis-
facibilidad a L y L a L , entonces satisfacibilidad a L . Para mostrar que un problema de decisión
1 1 2 2
del tipo NP-difícil es NP-completo, solo se debe de mostrar un algoritmo de tiempo polinomial no
determinístico.
Los problemas de la clase NP-difícil (y su subconjunto NP-completo) se encuentran en una gran
variedad de disciplinas, como se muestra a continuación:
NP-HARD graph problems
• Clique Decision Problem (CDP).
• Node Cover Decision Problem.
• Chromatic Number Decision Problem (CN).
• Directed Hamiltonian Cycle (DHC).
• Traveling Salesperson Decision Problem(TSP).
• AND/OR Graph Decision Problem (AOG).
NP-HARD scheduling problems
• Scheduling Identical Processors.
• Flow Shop Scheluling.
179
