Decima puntata del nostro viaggio
Per completare il quadro della risoluzione algoritmica dei problemi, dobbiamo discutere ancora una situazione, estremamente importante nel contesto odierno. In base a quanto detto nel post precedente, possono esistere dei problemi per i quali non si conoscono algoritmi con funzione di complessità polinomiale (e quindi non si può dire che appartengono alla classe P), ma per cui non si è ancora trovata la dimostrazione di impossibilità di ottenerli (e quindi non si può dire che appartengono propriamente alla classe EXP). Ciò vuol dire che per essi si conosce almeno un algoritmo risolutivo (la cui funzione di complessità è esponenziale), e questo li classifica come problemi computabili, ma non si sa dire se siano problemi che appartengono alla varietà “buona” (cioè ammettono algoritmi polinomiali, ossia sono trattabili) oppure “cattiva” (con solo algoritmi esponenziali, cioè intrattabili). In questo caso il problema è in una specie di limbo, nel quale gli informatici teorici hanno individuato un insieme molto importante detto classe NP, che marca il confine fra la trattabilità e l’intrattabilità.
Senza entrare nel dettaglio di come tale classe venga definita (per cui rimando al libro La rivoluzione informatica), possiamo dire che ad essa appartengono i problemi le cui soluzioni sono verificabili in tempo polinomiale e per i quali si conoscono solo algoritmi risolutivi di complessità esponenziale. In effetti esistono centinaia di questi problemi (migliaia se ne consideriamo le varianti), per i quali è stata dimostrata l’equivalenza reciproca. Questa equivalenza vuol dire che se per uno solo di essi si trovasse un algoritmo polinomiale, allora tutti questi problemi rientrerebbero nella classe P (sarebbero, cioè, problemi trattabili). Se per uno solo di essi si dimostrasse invece l’appartenenza propria alla classe EXP, allora verrebbero tutti classificati come intrattabili (anche se quest’ultima ipotesi appare poco probabile alla maggior parte degli studiosi).
Allo stato attuale delle conoscenze dell’informatica teorica si sa che la classe P è strettamente contenuta nella classe EXP (ricordo che un insieme A è strettamente contenuto nell’insieme B se ogni elemento di A appartiene anche a B e inoltre si è certi dell’esistenza di elementi che appartengono a B e non appartengono ad A). Però, le relazioni note tra le classi P, NP ed EXP sono solo di contenimento, cioè che P è contenuta in NP e che NP è contenuta in EXP, ma non si sa esattamente quale di questi contenimenti sia stretto. L’aspetto più interessante riguarda la relazione tra le classi P e NP. Potrebbe essere stretto oppure le due classi potrebbero coincidere. Il problema se la classe P e la classe NP coincidano o meno, ovvero
P = NP?
è probabilmente il problema aperto più famoso dell’informatica teorica. Il Clay Mathematics Institute lo ha inserito nel 2000 fra i sette problemi del millennio e ha offerto un premio di un milione di dollari per la sua dimostrazione.
Il problema ha un interesse particolare dal momento che problemi nella classe NP che si pensa non siano in P sono spesso alla base dei metodi crittografici, che proteggono la sicurezza delle transazioni commerciali su Internet. Ad esempio, il sistema di cifratura a chiave pubblica RSA ha alla base della sua sicurezza il fatto che la scomposizione di un numero intero in fattori primi è uno di questi problemi.
Poiché non si conoscono, al momento attuale, algoritmi efficienti (cioè eseguibili in tempo polinomiale) per scomporre un intero nei suoi fattori primi, il sistema non può essere violato in un tempo accettabile. Va ricordato che, con sufficienti attrezzature hardware dedicate (che sono alla portata di organizzazioni di grandi dimensioni che possono contare su ingenti risorse economiche quali, ad esempio, l’NSA, acronimo di National Security Agency, l’agenzia per la sicurezza nazionale degli Stati Uniti) si riescono a scomporre interi di 1.024 bit, che era il valore raccomandato per la costruzione delle chiavi di RSA fino a qualche anno fa. Bruce Schneier, esperto USA di sicurezza, ha raccomandato nel 2007, quando è stata annunciata la scomposizione di un intero di circa 1.024 bit (anche se di un tipo particolare che ha reso il lavoro più semplice) di abbandonare le chiavi di questa lunghezza. La disponibilità di computer cosiddetti “quantistici” è un’altra possibile minaccia alla cifratura a chiave pubblica RSA, ma anche per questa eventualità si stanno prendendo le opportune contromisure.
( I post di questa serie sono basati sul libro dell’Autore La rivoluzione informatica: conoscenza, consapevolezza e potere nella società digitale, al quale si rimanda per approfondimenti. I lettori interessati al tema possono anche dialogare con l’Autore, su questo blog interdisciplinare. )