Notizia bomba per i nerds: Vinay Deolalikar degli Hewlett Packard Labs, un matematico delle reti, ha appena pubblicato in versione preliminare la prova che P ? NP (grazie a Juhan per il link).
Dico sul serio.
Se è corretta vince il milione di dollari del premio Clay per aver risolto uno dei problemi del millennio. E i crittografi e i loro clienti potranno dormire sonni tranquilli. Se P = NP, tutta la crittografia è da rifare, lavoro assicurato per decenni. D’altronde i problemi NP potrebbero avere una soluzione generale e semplice, pour ainsi dire. E tantissime ricerche (pensate alle neuroscienze o meglio alla biologia: segnali, geni pleiotropici, i-Rna, proteine, vaccini, farmaci…) in cui bisogna identificare la combinazione giusta tra migliaia o milioni di possibilità diventerebbero banali e più veloci perché i computer ci arriverebbero da soli. Toujours pour ainsi dire.
La prova regge? Aggiornamenti sul putiferio da Richard Lipton (cross posted con qualche spiegazione in più su Oggi Scienza).
.
Aggior.: c’è un wiki e fra i commenti nell’ultima puntata di R. Lipton, un sunto di Terry Tao molto no sulla prova e molto sì sulla soddisfazione di lavorare insieme. Sì, quel Terry Tao.