Problema NP difficile

Un problema si dice NP-difficile (NP-hard) quando è tanto difficile quanto i problemi più difficili in NP, ma non è necessario che esista un algoritmo in grado di verificare una soluzione in tempo polinomiale.

Questo vuol dire che l'insieme dei problemi NP difficili è più esteso della classe NP.

La classe NP comprende problemi per i quali le soluzioni possono essere verificate in tempo polinomiale.

I problemi NP-difficili, invece, includono qualsiasi problema tanto difficile quanto i problemi più complessi in NP, indipendentemente dal fatto che le soluzioni possano o meno essere verificate in tempo polinomiale.

Esempio

Un esempio classico di problema NP-difficile è il problema dell'arresto.

Questo problema chiede se, dato un programma informatico e un input per quel programma, il programma terminerà (si arresterà) o continuerà a girare all'infinito.

In altre parole, ci si domanda se fosse possibile costruire un algoritmo che possa determinare per ogni possibile programma e input se il programma si fermerà o meno.

Questo problema è NP-difficile perché se avessimo un modo per risolverlo in generale, potremmo risolvere qualsiasi altro problema in NP semplicemente costruendo un programma che cerca tutte le possibili soluzioni e si ferma solo quando ne trova una valida.

Tuttavia, il problema dell'arresto è noto per essere indecidibile perché non esiste un algoritmo che può risolverlo per ogni possibile programma e input.

Inoltre, il problema dell'arresto non ha soluzioni verificabili in tempo polinomiale, quindi è al di fuori della classe NP.