In un precedente articolo abbiamo definito i problemi decisionali, e in un altro articolo abbiamo definito le classi di complessità P, NP e co-NP. Rimandiamo il lettore a quei due articoli per la discussione.
Oggi riprendiamo la discussione partendo dalla classe di complessità NP-difficile; come dicevo, questi nomi sono pessimi e infatti in linea di massima NP-difficile ha una relazione non-banale con NP. Vediamo la definizione:
Definizione. Un problema X è NP-difficile se ogni problema in NP può essere efficientemente (cioè in tempo polinomiale) ridotto a X.
Ciò che vuol dire “riduzione” non è banale, e infatti ripetiamo che queste sono definizioni informali. In pratica vuol dire che dato un qualsiasi problema Y in NP, esiste un algoritmo polinomiale che converte un’istanza di Y in un’istanza di X.
In particolare ciò significa che se qualcuno trovasse un algoritmo polinomiale per risolvere un qualsiasi problema in NP-difficile allora ciò vuol dire che ogni problema in NP può essere risolto con un algoritmo polinomiale, e quindi P=NP. Evidentemente ciò non è noto, ma è ritenuto improbabile. Prima di dare degli esempi, procediamo con un’altra definizione:
Definizione. Un problema è in NP-completo se è sia in NP che in NP-difficile, ovvero NP-completo $=$ NP $\cap$ NP-difficile.
Non è per niente ovvio che esistano problemi (quantomeno problemi “naturali”) in NP-completo. Tuttavia esistono. Ad esempio il cosiddetto problema “3-SAT” è in NP-completo, come vedremo nel prossimo articolo. Un altro esempio di problema NP-completo è il problema decisionale del commesso viaggiatore, che abbiamo visto nel precedente articolo. Esistono anche problemi NP-difficili che non sono in NP (e quindi non sono in NP-completo), come ad esempio il problema della terminazione, che però è indecidibile; altri esempi sono piuttosto complicati. Una lista di altri problemi NP-completi si trova su wikipedia.
Giusto per chiarci le idee, possiamo quindi tirare una somma con questo grafico preso da Wikipedia:
Come vedete, l’immagine dipende dalle ipotesi su P e NP. In particolare consideriamo la prima immagine, in cui P $\neq$ NP (considerata l’ipotesi più probabile). In tal caso nessun problema NP-difficile è in P (altrimenti P=NP come abbiamo detto sopra) e quindi P e NP-difficile sono disgiunti. Inoltre abbiamo il seguente risultato:
Teorema (Ladner). Se P $\neq$ NP allora esistono problemi in NP che non sono né in P né in NP-difficile.
Ciò vuol dire che il disegno è corretto, e quindi esistono problemi non risolubili ma verificabili in tempo polinomiale, a cui però non è possibile ridurre tutti gli altri problemi in NP. La classe di questi problemi è nota come NP-intermedio. Si congettura che la fattorizzazione di un intero è in questa classe (abbiamo infatti visto che è in NP, ma non è noto nessun algoritmo polinomiale) così come l’isomorfismo di grafi (per cui il miglior algoritmo noto è quasi-polinomiale). Chiaramente dimostrare che un problema è in NP-intermedio (e quindi in NP ma non in P) è equivalente a dimostrare che P $\neq$ NP.
Al contrario se P=NP allora P= NP-completo (perché in generale esistono problemi NP-completi e quindi se P=NP allora tutti i problemi in NP, inclusi quelli NP-completo, hanno soluzione polinomiale, come abbiamo visto prima). Ciò non implica che tutti i problemi NP-difficile siano risolubili polinomialmente, ma soltanto quelli che sono NP-completi.
Con questo articolo concludiamo la discussione delle classi di complessità. Menzioniamo alcuni altre cose correlate. Prima di tutto che esistono altre classi di complessità per problemi di tipo diverso (cioè non decisionali): ad esempio la classe #P (e altre classi correlate) per i problemi di conteggio. Inoltre la discussione è valida per i computer classici. Esistono algoritmi quantistici polinomiali per risolvere alcuni problemi (tipo la fattorizzazione di un intero) per cui non è noto nessun algoritmo polinomiale classico. Tuttavia in generale si ritiene (ma non c’è una dimostrazione) che i computer quantistici non siano in grado di risolvere problemi NP-difficili.