NP-Difícil

La clase NP-Difícil (NP-Hard) es una categoría fundacional de la teoría de complejidad computacional y agrupa los problemas a los que todo problema de NP se reduce en tiempo polinomial. El concepto fue establecido por Cook (1971), quien demostró que la satisfacibilidad booleana (SAT) es NP-completa, y por Karp (1972), que probó veintiún problemas combinatorios NP-completos mediante reducciones polinomiales, anclando la categoría en la IO práctica. Un problema que está en NP y a la vez es NP-Difícil se denomina NP-Completo; si no está en NP, aún puede ser NP-Difícil (por ejemplo, la versión de optimización del TSP). Problemas NP-Difíciles clásicos: vendedor viajante (TSP), mochila, coloración de grafos, set covering, ruteo de vehículos, job shop scheduling, minimización del makespan, bin packing y muchas formulaciones de programación entera mixta (MIP). La pregunta P = NP es un problema matemático abierto; en la práctica, todo algoritmo exacto conocido para problemas NP-Difíciles requiere tiempo exponencial en el tamaño de la entrada. Esto ha impulsado el desarrollo de heurísticas, metaheurísticas y algoritmos de aproximación. Garey y Johnson (1979) es la referencia para pruebas de NP-completitud. La clasificación NP-Difícil señala al profesional que abandone la expectativa de solución exacta directa y opte por relajación, descomposición o enfoques heurísticos.