P contro NP: il problema da un milione di dollari dell'informatica

Esiste una domanda apparentemente semplice che, se trovasse risposta, varrebbe un milione di dollari e potrebbe riscrivere il funzionamento di internet, della crittografia e di interi settori della scienza. La domanda è questa: se siamo capaci di verificare velocemente la soluzione di un problema, siamo anche capaci di trovarla velocemente? In gergo matematico si scrive P contro NP (P vs NP), ed è considerato uno dei più grandi enigmi irrisolti della matematica e dell'informatica.

Non è un'astrazione per soli addetti ai lavori: la risposta tocca da vicino la sicurezza dei nostri dati bancari, delle password e di gran parte delle comunicazioni digitali.

Trovare è più difficile che controllare

Per capire il problema, pensiamo a un puzzle. Comporre un puzzle da mille pezzi può richiedere ore di tentativi. Ma verificare che un puzzle sia stato completato correttamente è questione di un colpo d'occhio. Trovare la soluzione e controllarla sono due cose molto diverse. La classe P raccoglie i problemi che un computer può risolvere in tempi ragionevoli (in termini tecnici, "polinomiali"). La classe NP raccoglie i problemi la cui soluzione, una volta proposta, può essere verificata in tempi ragionevoli, anche se trovarla potrebbe essere difficilissimo.

La domanda da un milione di dollari è: queste due classi coincidono? Cioè, P è uguale a NP? Se la risposta fosse sì, significherebbe che ogni problema facile da controllare è anche, in linea di principio, facile da risolvere. La maggior parte degli esperti, però, è convinta del contrario, cioè che P sia diverso da NP, ma nessuno è ancora riuscito a dimostrarlo.

Una questione da un milione di dollari

Il problema fu formulato in modo preciso nel 1971 dall'informatico Stephen Cook nel suo articolo "The complexity of theorem proving procedures", e in modo indipendente, poco dopo, dal matematico sovietico Leonid Levin. Nel 2000 il Clay Mathematics Institute lo ha inserito tra i sette Problemi del Millennio, i grandi quesiti irrisolti della matematica, mettendo in palio un milione di dollari per chi fornisse la prima dimostrazione corretta. Ad oggi quel premio è ancora lì, intatto.

Va detto che dei sette problemi del millennio uno solo è stato risolto: la congettura di Poincaré, dimostrata dal matematico russo Grigori Perelman, che peraltro rifiutò il premio. P vs NP resta invece tra i più resistenti, come ricostruisce anche la voce P versus NP problem dell'enciclopedia.

Perché riguarda la sicurezza di internet

Qui la faccenda diventa concreta. Gran parte della crittografia moderna si fonda su un'assunzione precisa: che certi problemi matematici siano facili da verificare ma praticamente impossibili da risolvere in tempi utili. Per esempio, moltiplicare due grandi numeri primi è facile, ma fare il percorso inverso — scomporre il risultato nei suoi fattori primi — è enormemente più difficile, e su questa asimmetria si basano molti sistemi che proteggono pagamenti, messaggi e password.

Se qualcuno dimostrasse che P = NP ed esibisse un metodo pratico per risolvere questi problemi velocemente, l'intera impalcatura della sicurezza digitale crollerebbe: password, transazioni bancarie e comunicazioni cifrate diventerebbero potenzialmente violabili. Come sottolinea anche un approfondimento della banca BBVA, è una delle ragioni per cui questa domanda astratta ha conseguenze tutt'altro che teoriche.

Un enigma che resta aperto

Va però chiarito un punto: anche se un giorno si dimostrasse che P = NP, non è detto che il disastro sia immediato. La dimostrazione potrebbe essere "non costruttiva", cioè provare che una soluzione veloce esiste senza fornire il metodo per trovarla, oppure produrre algoritmi così lenti nella pratica da risultare inutilizzabili. Allo stesso modo, una prova che P ≠ NP confermerebbe ciò che molti già sospettano, ponendo basi solide alla crittografia attuale.

Nel frattempo, la domanda continua a sfidare le menti più brillanti del pianeta. È raro che un problema così facile da enunciare — "trovare è davvero più difficile che controllare?" — si riveli così spaventosamente difficile da risolvere. E forse è proprio questa la sua bellezza.