NP-Difficile

La classe NP-Difficile (NP-Hard) è una categoria fondante della teoria della complessità computazionale e raccoglie i problemi a cui ogni problema in NP si riduce in tempo polinomiale. Il concetto è stato stabilito da Cook (1971), che ha dimostrato la NP-completezza della soddisfacibilità booleana (SAT), e da Karp (1972), che ha provato la NP-completezza di ventuno problemi combinatori tramite riduzioni polinomiali, ancorando la categoria alla RO pratica. Un problema che è sia in NP sia NP-Difficile è detto NP-Completo; se non è in NP può comunque essere NP-Difficile (es. la versione di ottimizzazione del TSP). Problemi NP-Difficili classici: commesso viaggiatore (TSP), zaino, colorazione di grafi, set covering, vehicle routing, job shop scheduling, minimizzazione del makespan, bin packing e molte formulazioni di programmazione intera mista (MIP). La questione P = NP resta un problema matematico aperto; in pratica ogni algoritmo esatto noto per problemi NP-Difficili richiede tempo esponenziale nella dimensione dell'input. Ciò ha alimentato lo sviluppo di euristiche, metaeuristiche e algoritmi di approssimazione. Garey e Johnson (1979) è il riferimento per le dimostrazioni di NP-completezza. La classificazione NP-Difficile segnala al professionista di abbandonare l'aspettativa di soluzione esatta diretta e scegliere rilassamento, decomposizione o approcci euristici.