Il problema è molto semplice: esistono problemi per i quali è facile stabilire se una certa risposta è quella giusta, ma per i quali però è molto difficile trovare questa risposta? Se si, P è diverso da NP, altrimenti è uguale. Ed è un problema che vale un milione di dollari…
di Giovanni Felici
Come non rimpiangere i bei tempi in cui durante il torrido agosto si andava in ferie e si prendeva il sole ? La globalizzazione scientifica ha invece tenuto occupati i giorni (e le notti, certamente) agostani per molti preziosi cervelli di tutto il mondo. L’argomento? un’altra “dimostrazione” (le virgolette sono d’obbligo) della famosa congettura di Cook P=NP (1971), di cui già si disse in queste pagine pochi mesi fa. Il problema è molto semplice: esistono problemi per i quali è facile stabilire se una certa risposta è quella giusta, ma per i quali però è molto difficile trovare questa risposta? Se si, P è diverso da NP, altrimenti è uguale. Facile e difficile, in questo caso, si riferiscono alla velocità con cui il tempo necessario alla soluzione di questi problemi cresce al crescere della dimensione dei dati che li descrivono. Dall’ultima volta che ne abbiamo parlato, nessuno si è ancora aggiudicato il premio di 1 milione di dollari messo in palio dalClay Mathematical Institute. Ci ha provato, il 9 agosto scorso, Vinoy Deolalikar, Principal Research Scientist degli HP Labs, che ha reso pubblica una dimostrazione di circa 100 pagine dove si dimostrerebbe che P è diverso da NP (P ¹NP). Il Dottor Deolalikar è un fine logico matematico, con ottime competenze in statistica e algoritmi randomizzati, e la sua dimostrazione impiega diversi strumenti, fra cui le strutture deiproblemi random k-SAT e risultati della Finite Model Theory. Insomma, un prodotto scientifico di altissimo livello. Dopo la sua uscita pubblica si è alzato però sul web un fuoco incrociato decisamente poco paragonabile alle procedure di referaggio usate solitamente dalle riviste scientifiche blasonate: comunicazioni rapide, scambi di email con l’autore del lavoro per suggerire correzioni o aggiustamenti in alcuni punti critici della dimostrazione… e, a voler giudicare da alcuni illustri pareri, ci sono un paio di passaggi che proprio non vanno: sembra infatti che il P cui Vinoy si riferisce nella dimostrazione sia ad esempio un po’ diverso da come dovrebbe essere per la completa dimostrazione del teorema, e che, inoltre, egli assuma che i problemi facili hanno spazi delle soluzioni facili, assunzione con cui molti non sono d’accordo (ma gli aggiornamenti in tempo reale sulla questione li trovate nel blog di Dick Lipton). Del resto, volendo usare anche noi un approccio statistico (lo stesso che usa Deolalikarin alcuni passaggi della sua dimostrazione) possiamo andare a guardare il sito The_P_versus-NP_page per scoprire che, dal 1996 ad oggi, sono stati proposti 30 lavori scientifici che dimostrano che P = NP, e 24 che dimostrano, ovviamente, il contrario. Nessuna di queste dimostrazioni è stata accettata come valida dalla comunità scientifica dopo più o meno ponderosi peer reviews. Auguriamo quindi a Vinoy di avere colto nel segno – finalmente – e di incassare il lauto premio, sempre che non debba dividerlo con tutti quelli che gli hanno inviato suggerimenti e correzioni sul web (nel qual caso, gli basterebbero appena per una pizza). Al momento, la strada per la fama eterna per il geniale scienziato aziendale appare abbastanza ripida… tenendo infine presente che l’eventuale dimostrazione di P ¹NP avrebbe quasi un sapore di restaurazione rispetto al più rivoluzionario effetto che avrebbe la dimostrazione della identità dei due insiemi. Nel primo caso, infatti, gli scienziati potranno continuare a cercare le soluzioni ai problemi difficili accontentandosi di trovare qualcosa che funziona abbastanza bene. Ma non è così che gira il mondo?
Giovanni Felici è laureato in Scienze Statistiche presso l’Università Sapienza di Roma, dove ha conseguito il dottorato in Ricerca Operativa nel 1995. Dal 1998 è ricercatore presso l’ Istituto di Analisi dei Sistemi ed Informatica (IASI) del Consiglio Nazionale delle Ricerche.
