P è diverso da NP

E tanto meglio per le transazioni on line

di Alessio Palmero Aprosio

Dopo decenni di tentativi non riusciti, il più annoso problema dell’informatica moderna sembra finalmente aver trovato una soluzione. L’indiano Vinay Deolalikar, ricercatore presso Hewlett-Packard, ha consegnato alla comunità scientifica un paper che potrebbe finalmente dare una risposta al problema definito “P contro NP”. Prima di Deolalikar, altri illustri matematici e informatici si erano cimentati nel problema, ma nessuno di loro era mai riuscito a fornire una soluzione soddisfacente.

Il problema in questione riguarda una branca dell’informatica detta “complessità computazionale”, che si occupa di studiare il numero di operazioni necessarie per processare un determinato calcolo. Se dobbiamo sommare 3 + 5 facciamo una sola operazione, mentre per stabilire che 23 è un numero primo dobbiamo eseguirne parecchie (ad esempio provare la divisione di 23 per ogni numero ad esso minore). Senza entrare troppo nel dettaglio, i problemi più semplici appartengono al gruppo P, mentre quelli più complessi vengono inclusi in NP. La domanda a cui per decenni si è tentato di rispondere è: P è uguale a NP oppure i due insiemi sono diversi? La tesi del ricercatore indiano confermerebbe ciò che i matematici di tutto il mondo pensano da anni: P è diverso da NP.

Anche se sembra un problema astratto per teste d’uovo, in realtà il problema ha radici profondissime nella vita di tutti i giorni. Tutti i sistemi informatici on line considerati “sicuri”, come ad esempio quelli che gestiscono i nostri pagamenti tramite carta di credito, si basano sul presupposto, fino a ieri mai dimostrato, che P fosse diverso da NP. Se la dimostrazione di Vinay Deolalikar si rivelerà corretta, banchieri ed esperti di sicurezza potranno finalmente tirare un sospiro di sollievo e i nostri conti correnti bancari potranno continuare a essere considerati sicuri.

La gloria, tuttavia, non sarà l’unica cosa che l’informatico indiano porterà a casa se e quando la sua dimostrazione verrà confermata da un’accurata analisi da parte dei suoi colleghi. Lo aspetta anche il famoso premio in denaro del Clay Mathematics Institute, che nel 2000 istituì i Millennium Prize Problems, consistenti in sette premi in denaro rispettivamente per la soluzione di altrettanti problemi della matematica moderna. Si parla di sette milioni di dollari in totale, di cui uno solo è stato assegnato per la soluzione della congettura di Poincaré da parte del matematico russo Grigori Perelman, che però lo ha rifiutato. Il prossimo potrebbe essere per Vinay Deolalikar.

Un ingegnere del Massachusetts Institute of Technology, Scott Aaronson, colpito dall’eleganza della soluzione proposta dal ricercatore di Hewlett-Packard sul problema di P e NP, ha dichiarato sul suo blog che aggiungerà personalmente 200 mila dollari al premio una volta che la dimostrazione sarà stata verificata.