In informatica, si sente spesso parlare di diverse classi di complessità computazionale. In questo articolo vediamo alcune di queste classi e l’idea dietro ognuna di esse.
Prima di tutto, le classi di complessità, P, NP, ecc. hanno a che fare con problemi decisionali. Ovvero problemi la cui soluzione è una risposta sì o no. In un precedente articolo, che consigliamo al lettore, abbiamo parlato dei problemi decisionali e del modo in cui moltissimi problemi non-decisionali possono essere considerati come problemi decisionali. Ciò rende molto grande l’applicabilità delle classi P, NP. Rimandiamo all’articolo precedente anche per una rapida spiegazione della complessità computazionale. Cominciamo col dare una definizione:
Definizione. Un problema decisionale è nella classe P se è risolvibile con un algoritmo di tempo polinomiale.
Ricordiamo che in pratica “tempo polinomiale” vuol dire “risolvibile in maniera efficiente”. Per dimostrare che un problema è in P basta ad esempio esibire un algoritmo che lo risolve in tempo polinomiale. Tuttavia il contrario è meno banale: ovvero anche se non conosciamo nessun algoritmo polinomiale per risolvere un problema, ciò non vuol dire a priori che non esista: va dimostrato.
Ad esempio, supponiamo di voler determinare se un numero $N$ è primo. L’algoritmo banale controllerebbe la divisione per ogni intero $\leq \sqrt{N}$, e quindi nel caso peggiore impiegherebbe $\mathcal{O} \sqrt{N}) \approx \mathcal{O}(2^{n/2})$ che è esponenziale nel numero di bit $n$ di $N$. Tuttavia esistono algoritmi migliori, in particolare un algoritmo (l’algoritmo APR) quasi-polinomiale, ovvero la cui complessità è della forma $\approx \mathcal{O}(2^{c\log{n}^q})$. È stato poi trovato un algoritmo polinomiale, ovvero l’algoritmo AKS. Perciò sappiamo ora che questo problema è in P.
Esistono tanti diversi esempi di complessità, e sarebbe antieconomico creare una classe di complessità per ognuno. La nozione interessante, invece non dipende dalla difficoltà di trovare la soluzione:
Definizione ($\approx$). Un problema decisionale è nella classe NP se la soluzione è verificabile con un algoritmo di tempo polinomiale.
Ciò vuol dire che $P \subset NP$, perché se posso trovare la soluzione in tempo polinomiale allora per verificare che la soluzione sia corretta è sufficiente trovare la soluzione e controllare che sia uguale a quella fornita. Perciò ogni problema in P è anche in NP. I nomi di queste classi computazionali sono purtroppo pessimi, e ci dicono ben poco sul loro significato (no, NP non significa “non-polinomiale”). Perciò:
Proposizione. P $\subset$ NP.
Perché abbiamo messo il simbolo di approssimazione? Prima di tutto perché stiamo dando delle definizioni informali, e ciò è vero di tutto l’articolo: per rendere tutto formalmente rigoroso sono necessarie ulteriori precisazioni. In questo caso le evitiamo per rendere le cose più semplici. Ma anche in maniera informale, la definizione sopra ci potrebbe far cadere in errore. Una definizione più precisa è la seguente:
Definizione (più precisa). Un problema decisionale è nella classe NP se la soluzione “sì” è verificabile con un algoritmo di tempo polinomiale dato un certificato di soluzione.
Questa definizione è più complicata, ma è anche necessaria. Innanzitutto il fatto che la risposta “sì” non sia la stessa cosa della risposta “no”: abbiamo infatti anche la definizione seguente:
Definizione (più precisa). Un problema decisionale è nella classe co-NP se la soluzione “no” è verificabile con un algoritmo di tempo polinomiale dato un certificato di soluzione.
Chiaramente formulando la domanda in maniera diversa, è possibile passare dal problema che dà come risposta “sì” a quello che dà come risposta “no”; ciò che non è detto è che entrambe le risposte siano facilmente verificabili. Può sembrare strano, ma non è noto se co-NP = NP. Altrimenti avremmo potuto evitare la distinzione. Tuttavia è noto che:
Proposizione. P $\subset$ NP $\cap$ co-NP.
Ciò non è sorprendente: abbiamo visto prima che P è in NP, e per lo stesso motivo in pratica è anche in co-NP. Tuttavia non è detto che i due siano uguali. Ad esempio (poiché controllare se un numero è primo è decidibile in tempo polinomiale) la fattorizzazione di interi è in NP $\cap$ co-NP (il certificato è la fattorizzazione), ma non è noto nessun algoritmo polinomiale per il problema.
Ora vediamo la questione del certificato. Chiaramente se accettassimo algoritmi che sputano solo “sì” o “no” e nient’altro, non ci sarebbe nessuna maniera di verificare la soluzione senza ricalcolarla. Perciò la classe NP (o co-NP) sarebbe inutile. Perciò chiediamo che l’algoritmo sputi non solo la soluzione (sì/no) ma anche un “certificato” che permetta di verificare la soluzione in tempo polinomiale.
Consideriamo un esempio concreto: supponiamo che il problema sia “l’intero $N$ è composito?” (ovvero non primo). Il certificato può essere semplicemente un fattore primo di $N$, che non sia $N$. In tal caso la risposta “sì” può essere verificata in tempo polinomiale semplicemente controllando che il certificato divide $N$. Ciò vuol dire che il problema è in NP. Al contrario supponiamo che la risposta sia “no”. Allora non è immediatamente chiaro quale certificato possa sputare l’algoritmo per permetterci di verificare il “no” in tempo polinomiale. Perciò non è immediatamente chiaro se il problema sia in co-NP. Tuttavia dalla discussione sopra sappiamo che in realtà il problema è in P (e quindi anche in co-NP).
Un altro problema chiaramente in NP è il problema del commesso viaggiatore. Come problema decisionale, ci chiede: “esiste un percorso di lunghezza inferiore ad $l$?” dove $l$ è un numero arbitrario. Se la risposta è sì, il certificato può essere banalmente il percorso stesso, per cui è facile calcolare la lunghezza. Perciò il problema è in NP. Se la risposta è “no”, invece non è per niente ovvio quale certificato si possa sputare per verificare che non esista nessun percorso inferiore ad $l$ in generale. Infatti non è noto se il problema sia in co-NP. Avremo altri esempi più avanti.
Per evitare delle risoluzioni banali, in realtà è richiesto anche (per entrambe le classi) che il certificato sia di grandezza polinomiale.
Uno dei problemi centrali dell’informatica teorica è determinare se P$=$NP. Il problema è aperto, anche se la maggioranza delle persone ritiene che P $\neq$ NP: ovvero che esistano problemi verificabili ma non risolvibili in tempo polinomiale. Nessuno però è mai stato in grado di dimostrare che ciò sia vero. Non è neanche noto se NP $=$ co-NP oppure NP $!=$ co-NP, sebbene la seconda possibilità sia ritenuta più probabile.
Dato che l’articolo è già molto lungo rimandiamo la discussione delle classi NP-difficile e NP-completo al prossimo articolo.