Il più grande problema dell’informatica: P contro NP

Esistono sette problemi matematici considerati così difficili e interessanti che il Clay Mathematics Institute li ha battezzati problemi del millennio: chi risolve uno di questi problemi riceve un premio di un milione di dollari. Uno di essi riguarda anche l’informatica e si chiama problema P contro NP. Vediamo di cosa si tratta davvero.

Mettiamola così: non illudiamoci che sia facile da spiegare. Dopotutto è un problema del millennio. Quindi vai a prepararti un buon tè verde 🍵 e iniziamo. Per prima cosa vedremo quattro problemi diversi del mondo dell’informatica e degli algoritmi. Li analizzeremo e scopriremo che rapporto hanno con le lettere P e NP.

Problema n. 1: trovare il numero più piccolo

P contro NP riguarda gli algoritmi e la loro complessità. Immagina che io rovesci davanti a te cento foglietti, su ognuno dei quali è scritto un numero, e ti chieda di trovare il foglietto con il numero più piccolo. Quanto tempo ti ci vorrà?

Mezzo minuto? Due minuti?

Queste sono unità di tempo che in informatica teorica non ci interessano granché. Ci interessa di più il numero di operazioni. Possiamo quindi porre la domanda in modo un po’ diverso: quanti foglietti devo controllare per essere sicuro di aver trovato il numero più piccolo? La risposta è che devo controllarli tutti, perché il numero più piccolo potrebbe trovarsi proprio sull’ultimo foglietto. Se davanti a te metto cento foglietti, devi controllarne cento. Se ne metto mille, devi controllarne mille. In generale, se davanti a te metto n foglietti, devi controllare n foglietti.

Questa si chiama complessità di un algoritmo. Se io metto davanti a te n foglietti e tu devi fare n operazioni per trovare il numero più piccolo, significa che l’algoritmo di ricerca del minimo ha complessità n, detta anche complessità lineare, perché la complessità è descritta da una funzione lineare.

Bene, hai passato in rassegna i cento foglietti e hai annunciato che il numero più piccolo è 17. Come faccio a controllare che dici la verità? Non c’è altro modo che riguardare tutti i foglietti e verificare che su nessuno ci sia un numero più piccolo. Insomma, tu hai dovuto guardare n foglietti per trovare il numero più piccolo e io, per controllarlo, devo fare lo stesso. Anche la complessità della verifica del risultato è dunque n, lineare.

Esistono algoritmi per i quali è più facile controllare il risultato che trovarlo?

Problema n. 2: il prodotto di una coppia

Immagina che io metta davanti a te due mucchietti di foglietti della stessa grandezza, con un numero su ogni foglietto. Ora ti chiedo di trovare un numero dal mucchietto A e un numero dal mucchietto B in modo che il loro prodotto sia 918. Ad esempio, prendiamo questi due mucchietti di numeri:

$\begin{array}{rcl} A & = & {49, 11, 32, 54, 15} \\ B & = & {17, 64, 74, 61, 21} \end{array}$

Come possiamo trovare una coppia di numeri con prodotto uguale a 918? Beh, possiamo semplicemente provare tutte le possibilità. Quante sono? Parecchie: 25. Cominciamo moltiplicando il primo numero del mucchietto A, cioè 49, per ogni numero del mucchietto B:

$\begin{array}{rcl} 49 \cdot 17 & = & 833 \\ 49 \cdot 64 & = & 3136 \\ 49 \cdot 74 & = & 3626 \\ 49 \cdot 61 & = & 2989 \\ 49 \cdot 21 & = & 1029 \end{array}$

Nessuna coppia dà 918. Proviamo allora lo stesso con gli altri numeri del mucchietto A: altre cinque coppie per l’11, altre cinque per il 32, altre cinque per il 54 e le ultime cinque per il 15. In tutto possiamo provare 25 coppie di numeri. Alla fine scopriamo che 54 · 17 = 918.

Qual è la complessità di questo algoritmo? Ci interessa quante coppie di numeri abbiamo dovuto moltiplicare. Entrambi i mucchietti contenevano cinque foglietti e abbiamo dovuto provare ciascuno dei cinque numeri del primo mucchietto con ciascuno dei cinque numeri del secondo. In tutto abbiamo provato 5 · 5 = 25 combinazioni. Se davanti a te mettessi due mucchietti da 10 foglietti, dovresti provare 10 · 10 = 100 combinazioni. In generale, se metto davanti a te due mucchietti da n foglietti, devi provare n · n = n² combinazioni.

Diciamo che questo algoritmo ha complessità n², complessità quadratica, perché è descritta da una funzione quadratica.

Ma quanto è difficile controllare il risultato? Se mi rispondi che 54 e 17 sono i numeri il cui prodotto è 918, non devo più passare in rassegna tutte le coppie dei due mucchietti, come hai dovuto fare tu. Mi basta moltiplicare questa sola coppia 54 · 17 per sapere se hai ragione o no. Quindi, mentre per risolvere il problema bisogna calcolare fino a n² prodotti, per la verifica basta calcolare un solo prodotto. La verifica ha dunque complessità costante 1.

In questo il problema si distingue nettamente dal precedente, dove per il calcolo vero e proprio e per la verifica successiva serviva lo stesso numero di passi.

Questo problema è anche molto più complesso del precedente. Se ti mettessi davanti diecimila foglietti e ti chiedessi di trovare il numero più piccolo, probabilmente ci riusciresti in una giornata. Ma se ti mettessi davanti due mucchietti da diecimila foglietti e ti facessi cercare il prodotto, dovresti controllare diecimila volte diecimila prodotti, cioè cento milioni di calcoli. Anche calcolando un prodotto al secondo, ti ci vorrebbero circa tre anni.

Problema n. 3: la somma di un sottoinsieme

Passiamo al terzo problema. Stavolta metto davanti a te dodici foglietti con dei numeri e ti chiedo di trovare un qualsiasi gruppo di foglietti la cui somma sia zero. Ad esempio:

$A = {24, - 69, 1, - 15, - 76, - 60, 16, - 83, 48, - 22, 54, - 47}$

Scegli da questi numeri un gruppo qualsiasi la cui somma dia 0. Per esempio i numeri

$24 + 48 - 69 + 1$

danno come somma 4, quindi non sono la risposta giusta. La risposta giusta è il gruppo di numeri… anzi, sai che c’è? Provaci tu come compito per casa 😉. Esiste un solo gruppo di numeri la cui somma dà 0. Almeno scoprirai di persona quanto è difficile questo problema.

Ora ci serve la complessità di questo problema. Il calcolo non è del tutto banale ed è più per intenditori. Se ti interessa come si calcola la complessità, continua a leggere. Altrimenti puoi saltare al paragrafo successivo. ⏩

Come possiamo trovare un gruppo di numeri la cui somma dà 0? Beh, dobbiamo semplicemente provare tutte le possibili combinazioni di numeri. Dobbiamo provare tutte le coppie, tutte le terne, le quaterne, le cinquine e così via, e per ogni gruppo verificare se la somma dà zero. Quante combinazioni esistono?

Vediamolo su un insieme più piccolo. Quanti gruppi diversi di numeri, cioè sottoinsiemi, posso formare con i tre numeri B = {5, 7, 9}? In tutto otto:

$\begin{array}{rcl} B_{1} & = & {} \\ B_{2} & = & {5} \\ B_{3} & = & {7} \\ B_{4} & = & {9} \\ B_{5} & = & {5, 9} \\ B_{6} & = & {5, 7} \\ B_{7} & = & {7, 9} \\ B_{8} & = & {5, 7, 9} \end{array}$

Nota che abbiamo contato anche il sottoinsieme vuoto B₁. Per ora non è molto utile, ma per completezza lo abbiamo lasciato. Per semplificare il calcolo, associamo a ogni sottoinsieme un vettore binario. Un vettore binario è semplicemente una successione di zeri e uni, per esempio 00101010. Noi lavoreremo con vettori binari di lunghezza tre. Associamo il vettore 101 al sottoinsieme che contiene «il primo e il terzo numero dell’insieme originale, ma non il secondo», cioè all’insieme {5, 9}. Il vettore 110 lo associamo al sottoinsieme che contiene «il primo e il secondo numero dell’insieme originale, ma non il terzo», cioè all’insieme {5, 7}, e così via.

$\begin{array}{rcl} B_{1} = {} & \to & 000 \\ B_{2} = {5} & \to & 100 \\ B_{3} = {7} & \to & 010 \\ B_{4} = {9} & \to & 001 \\ B_{5} = {5, 9} & \to & 101 \\ B_{6} = {5, 7} & \to & 110 \\ B_{7} = {7, 9} & \to & 011 \\ B_{8} = {5, 7, 9} & \to & 111 \end{array}$

Vediamo che a ogni sottoinsieme corrisponde esattamente un vettore binario di lunghezza tre. E ogni vettore binario di lunghezza tre corrisponde esattamente a un sottoinsieme. Quindi, se calcoliamo quanti vettori binari diversi di lunghezza n esistono, otteniamo il numero di combinazioni diverse che possiamo formare avendo in ingresso n numeri diversi. Facciamo il conto.

I vettori binari di lunghezza uno sono due: 0 e 1.

I vettori binari di lunghezza due si ottengono prendendo tutti i vettori binari di lunghezza uno e aggiungendo uno 0 in fondo a ciascuno: otteniamo 00 e 10. Poi prendiamo di nuovo tutti i vettori di lunghezza 1 e aggiungiamo in fondo 1: 01 e 11. Così abbiamo ottenuto tutti i vettori di lunghezza 2: 00, 01, 10 e 11.

I vettori binari di lunghezza tre si ottengono prendendo tutti i vettori binari di lunghezza due e aggiungendo in fondo uno zero: 000, 010, 100 e 110, e poi un uno: 001, 011, 101 e 111.

E così via per ogni lunghezza successiva. Vediamo che, quando aumentiamo di uno la lunghezza del vettore binario, il numero di vettori binari diversi raddoppia. Per la lunghezza quattro otterremmo quindi in tutto 2 · 2 · 2 · 2, cioè 16, combinazioni diverse.

In generale possiamo ricavare che, dato un insieme M di n elementi, il numero di tutti i sottoinsiemi di M è uguale al numero di tutti i vettori binari diversi di lunghezza n, ed è pari a

$\underset{n volte}{\underset{⏟}{2 \cdot 2 \cdot \dots \cdot 2}} = 2^{n}$

2ⁿ o n² – è la stessa cosa? Tutt’altro 🤷‍♂

Esistono dunque 2ⁿ sottoinsiemi diversi che possiamo formare con un insieme di n numeri. Nel nostro caso abbiamo n = 12 numeri, quindi dobbiamo controllare 2¹² combinazioni diverse, cioè 4096 combinazioni. Diciamo che questo problema ha complessità 2ⁿ, complessità esponenziale, perché è descritta da una funzione esponenziale.

Nota che il problema precedente aveva complessità n², mentre questo ha complessità 2ⁿ. Sembrano molto simili, vero? Eppure c’è una grande differenza tra avere un esponente costante e avere la variabile n all’esponente. Osserva che per n = 4 otteniamo

$\begin{array}{rclrc} n^{2} & = & 4^{2} & = & 16 \\ 2^{n} & = & 2^{4} & = & 16 \end{array}$

Bene, per ora i risultati coincidono. E se n = 10?

$\begin{array}{rclrc} n^{2} & = & 10^{2} & = & 100 \\ 2^{n} & = & 2^{10} & = & 1024 \end{array}$

Eh, la funzione esponenziale è partita in quarta ed è già circa dieci volte più grande di quella quadratica. Cosa otteniamo per n = 20?

$\begin{array}{rclrc} n^{2} & = & 20^{2} & = & 400 \\ 2^{n} & = & 2^{20} & = & 1 048 576 \end{array}$

Per n = 20 la complessità esponenziale vale circa 2600 volte quella quadratica. Vediamo dunque che la funzione esponenziale cresce molto più in fretta della funzione quadratica. Ricordatelo la prossima volta che una pandemia si diffonderà nella popolazione a ritmo esponenziale.

Se dunque mettessi davanti a te venti foglietti, dovresti controllare 1.048.576 combinazioni. Non è poco.

Come verifichiamo la correttezza del risultato?

Quanto ci metto a verificare che il gruppo di numeri trovato dia davvero somma 0? Molto poco: basta sommare quest’unico gruppo di numeri. Se la somma è 0, hai trovato il gruppo di foglietti giusto; se è diversa, il gruppo è sbagliato.

Ancora una volta vediamo che controllare il risultato è molto più semplice che trovarlo.

Problema n. 4: il problema del commesso viaggiatore

Il problema del commesso viaggiatore è uno dei problemi algoritmici più famosi. In parole povere, abbiamo un commesso viaggiatore che vende pioggia. E questo commesso viaggiatore deve viaggiare parecchio per guadagnarsi da vivere. Ha quindi deciso di visitare 14 grandi città italiane. E siccome non vuole sprecare niente, ha deciso di trovare il percorso più breve possibile che lo porti in tutte queste città. Il nostro compito è trovare questo percorso più breve.

Come possiamo trovarlo? Proviamo tutte le possibilità.

Possiamo semplificare le cose. Immaginiamo che tra due città qualsiasi esista esattamente un percorso più breve. Come possiamo trovare il percorso più breve che tocca tutte le città? Le città sono 14, quindi abbiamo 14 possibilità per scegliere da dove partire. Diciamo che siamo partiti da Bologna!!! Dove possiamo andare da Bologna? In teoria possiamo andare in una qualsiasi delle altre città. Possiamo quindi scegliere tra le 13 città rimanenti.

Già ora possiamo calcolare che abbiamo in tutto 14 · 13 possibilità per visitare le prime due città: ci sono 14 possibilità per la partenza e poi 13 città rimanenti tra cui scegliere.

Quando arriviamo nella seconda città, dobbiamo proseguire. In due città ci siamo già stati, quindi possiamo partire per una delle 12 città rimanenti. Abbiamo così in tutto 14 · 13 · 12 possibilità per visitare le prime tre città.

Dopo aver visitato la terza città, dobbiamo sceglierne una delle 11 rimanenti, poi una delle 10 rimanenti e così via.

Alla fine scopriamo che avevamo da scegliere tra

$14 \cdot 13 \cdot 12 \cdot 11 \cdot 10 \cdot 9 \cdot 8 \cdot 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1$

possibilità. Questo ti ricorderà il fattoriale, che si indica con il punto esclamativo. Possiamo quindi dire che questo prodotto è uguale a 14!:

$14! = 14 \cdot 13 \cdot 12 \cdot 11 \cdot 10 \cdot 9 \cdot 8 \cdot 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1$

e dunque esistono 14! percorsi che passano per tutte e 14 le città. Sono tanti? Direi di sì, perché

$14! = 87 178 291 200.$

In generale, se cercassimo il percorso più breve tra n città, dovremmo provare n! percorsi diversi. La complessità di questa soluzione è quindi n!.

Come verificheremmo di aver trovato il risultato giusto? Se mi dicessi che il percorso più breve va da Torino a Bari, poi a Napoli e così via, come faccio a controllare che dici la verità? Beh, è dura 🤷‍♂. Perché guardando quel percorso non ho modo di verificare facilmente che sia proprio il più breve. In pratica devo rifare tutto il calcolo da capo. Anche la complessità della verifica del risultato è quindi n!.

Le classi P e NP

Abbiamo visto quattro problemi e gli algoritmi che li risolvono e abbiamo analizzato quanto è difficile trovare la soluzione e quanto è difficile controllarla. Possiamo riassumere tutto in questa tabella:

Problema	Complessità della soluzione	Complessità della verifica
Numero più piccolo	n	n
Prodotto di una coppia	n²	1
Somma di un sottoinsieme	2ⁿ	n
Commesso viaggiatore	n!	n!

Ora dividiamo i nostri problemi in due gruppi. Il primo gruppo è formato dai problemi facili da risolvere. Sono i problemi che si possono risolvere con complessità n, oppure n², oppure n³, n⁴ e così via. Poiché espressioni come n² si chiamano polinomi, questa classe di problemi si indica con la lettera P. Diciamo dunque che la classe P contiene i problemi che si possono risolvere in tempo polinomiale (= hanno complessità, per esempio, n² o n⁷). In generale sono i problemi che si possono risolvere più o meno facilmente.

Nella classe P rientrano quindi il problema n. 1, trovare il numero più piccolo, perché la sua complessità è n, e il problema n. 2, il prodotto di una coppia, perché la sua complessità è n²: entrambi sono polinomi.

La seconda classe è la classe NP. Contiene i problemi che si possono verificare in tempo polinomiale. Nella classe NP rientrano quindi tutti i problemi tranne l’ultimo. Il problema del commesso viaggiatore non sappiamo verificarlo in tempo polinomiale. I tre problemi precedenti si possono verificare in tempo polinomiale.

Il problema del commesso viaggiatore non sappiamo né risolverlo né verificarlo in tempo polinomiale. Per questo problema ci servirebbe quindi un’altra classe ancora, che contenga problemi ancora più difficili. Questa classe esiste, ma per ora non ci interessa.

È evidente che la classe P è un sottoinsieme della classe NP. Cioè ogni problema della classe P è anche nella classe NP. Ha senso: se siamo in grado di risolvere un problema in tempo polinomiale, siamo in grado anche di verificare il risultato in tempo polinomiale.

Il problema P contro NP

E vale anche il contrario? Ogni problema della classe NP è anche nella classe P? Cioè, se esiste un modo di verificare il risultato di un problema in tempo polinomiale, esiste anche un algoritmo che risolve quel problema in tempo polinomiale?

Per esempio, sappiamo di essere in grado di verificare il risultato del problema n. 3, la somma di un sottoinsieme, in tempo polinomiale. Ma per risolverlo abbiamo usato un algoritmo che non è polinomiale: l’algoritmo usato ha complessità esponenziale 2ⁿ. Siamo però sicuri che per questo problema non esista nessun algoritmo con complessità polinomiale?

Non lo sappiamo!

Potrebbe benissimo darsi che per ogni problema che si può verificare in tempo polinomiale esista un algoritmo che lo risolve in tempo polinomiale. Noi non lo sappiamo. Non sappiamo dimostrare l’esistenza di un tale algoritmo, ma non sappiamo nemmeno dimostrare che non esiste.

Se per ogni problema della classe NP esistesse un algoritmo che lo risolve in tempo polinomiale, ne seguirebbe che la classe NP sarebbe in realtà uguale alla classe P. Tutti i problemi della classe P sarebbero nella classe NP e tutti i problemi della classe NP sarebbero nella classe P: le due classi coinciderebbero.

Il problema P contro NP è dunque la domanda se la classe P coincida con la classe NP, oppure se si tratti di due classi di problemi diverse.

O vale dunque P = NP, oppure vale P ≠ NP. Nessuno lo sa e, se lo scopri, ti aspettano un milione di dollari, gloria imperitura e con ogni probabilità anche il Premio Turing, una specie di Nobel per gli informatici.

Cosa succederebbe se P = NP?

Cosa succederebbe se valesse P = NP? Beh, non è facile dirlo con precisione. Sapremmo che per tutti i problemi della classe NP esiste un algoritmo che li risolve in tempo polinomiale. Per esempio, che per il nostro problema n. 3, la somma di un sottoinsieme, esiste un algoritmo che lo risolve in tempo polinomiale. Ma c’è un «ma», anzi tre:

Sapere che un tale algoritmo esiste non significa essere in grado di trovarlo. Sapremmo semplicemente che sì, esiste un algoritmo che risolve il problema in tempo polinomiale, ma magari non saremmo in grado di costruirlo per altri cento anni. È un po’ come quando la relatività generale previse l’esistenza dei buchi neri, ma ci sono voluti ancora diversi decenni prima di riuscire a scattare la prima «fotografia» di un buco nero.
Il fatto che esista un algoritmo che lavora in tempo polinomiale purtroppo non significa ancora che sia veloce. Potremmo trovare un algoritmo con complessità n¹⁰⁰. Anche l’espressione n¹⁰⁰, infatti, è un polinomio. Se confrontiamo le complessità 2ⁿ e n¹⁰⁰, vediamo che finché n è relativamente piccolo l’algoritmo con complessità 2ⁿ ha ancora bisogno di meno operazioni. Per esempio, per n = 20 vale 2²⁰ = 1.048.576, mentre l’espressione 20¹⁰⁰ dà un numero di circa 130 cifre, che è più grande di 1.048.576 di circa 120 ordini di grandezza. Il nostro algoritmo polinomiale sarebbe quindi, nella realtà, più lento di quello esponenziale. Almeno finché n è relativamente piccolo.
Se riuscissimo comunque a trovare un algoritmo veloce che lavora in tempo polinomiale, potremmo risolvere molti problemi più in fretta e con maggiore precisione. Ovviamente è una buona notizia, ma ha anche i suoi lati negativi. Esiste un settore che si basa sul fatto che alcuni problemi siano difficili da risolvere, ed è la crittografia, cioè la cifratura. Potrebbe quindi succedere che violare le cifrature attuali diventi molto più semplice.

Intermezzo: visto che sei arrivato fin qui, per premio ti svelo che la soluzione del problema n. 3 è 24 + 1 − 60 + 16 − 83 + 48 + 54.

Cosa succederebbe se P ≠ NP?

Se le classi di problemi P e NP fossero diverse, non cambierebbe granché, perché è più o meno lo status quo. Al momento non abbiamo nessun algoritmo che risolva in tempo polinomiale un problema difficile della classe NP e, se qualcuno dimostrasse che P ≠ NP, le cose resterebbero semplicemente così per sempre. Molto più sensazionale sarebbe la dimostrazione che P = NP.

Riferimenti nella cultura pop

In un episodio dei Simpson vediamo Homer finire in una specie di realtà alternativa in cui gli si rivela che P = NP. Lo trovi su youtube.com.
In Futurama, invece, in un magazzino ci sono due cartelle, una intitolata P e l’altra intitolata NP. Lo trovi su youtube.com.
Il secondo episodio della seconda stagione della serie Elementary, intitolato «Equazione mortale» (in originale «Solve for X»), ruota attorno all’omicidio di un matematico che aveva probabilmente risolto il problema P contro NP.

« Precedente: Quanto fa 1 + 2 + 5 · 0? La precedenza della moltiplicazione

Successivo: Il metodo Trachtenberg per l’addizione veloce »