Il  Cover Article  della rivista  ACM  di settembre ha registrato un notevole successo – tanto da meritarsi l’attenzione del New York Times  dello  scorso 7 ottobre.  Ma c’è poco da stupirsi, quando  viene dibattuta  l’identità tra le classi di problemi denominate “P” e “NP”, un argomento alla cui soluzione  sono interessati in molti. Il blasonato quotidiano già nel  1988  raccontava ai suoi lettori dei nuovi strumenti di calcolo sviluppati alla AT&T per la soluzione del classico problema del commesso viaggiatore, riprendendo l’argomento nel  1991  in  una estesa survey sugli avanzamenti della scienza sull’argomento.

La congettura  in questione –“P è uguale a NP ?”– sintetizza un problema fondamentale della informatica e della teoria della complessità. Ma quali problemi compongono le classi NP e P? Alla prima appartengono quei problemi per i quali si può verificare in un tempo “ragionevole” la correttezza di una soluzione data. La seconda contiene i problemi  della  prima classe per i quali è anche possibile trovare una soluzione corretta in un tempo “ragionevole”. Nessuno finora ha saputo dimostrare se le due classi coincidano o meno: se esistono, cioè, problemi facili da verificare ma difficili da risolvere. Si hanno molti esempi di problemi che sembrerebbero avere queste caratteristiche, come quello citato del  commesso viaggiatore, ma il fatto che per questi non si siano trovati metodi rapidi di soluzione non dimostra che tali metodi non esistano. Problemi di questo tipo sono frequenti in molti altri settori di forte interesse economico e sociale  – fra cui logistica,  distribuzione, crittografia. La dimostrazione della congettura avrebbe conseguenze sensazionali per la scienza, ma anche ricadute immediate nel mondo della tecnologia e della produzione, rendendo possibile sapere se una soluzione di un certo problema è veramente la migliore tra tutte le possibili o se ha senso spendere tempo a cercarne un’altra.

Un bel  dilemma, visto che dal 1971 nessuno è riuscito ancora a dare una risposta. A chi ancora dubitasse delle motivazione dei ricercatori a risolvere questo innocente rompicapo, ricordiamo  che questo è annoverato tra i “Problemi del Millennio” (tra cui, fino al 1995,  ha goduto  della compagnia del forse più letterario  ultimo teorema di Fermat) e che  sono in palio ben  un milione di dollari per il suo  risolutore.

Lance Fortnow, autore dell’articolo, ci conferma però che non si vede ancora luce in fondo al tunnel, ed indica altri non ancora utilizzati strumenti della matematica (ad esempio, la geometria algebrica) come candidati a fornire la soluzione della congettura. Ma come sanno i veri viaggiatori,  più della  meta conta il viaggio stesso: il percorso della ricerca verso la dimostrazione della congettura ha infatti consentito di  scoprire nuovi metodi di calcolo e algoritmi sempre più efficaci per aggirare la difficoltà dei problemi in NP. A volte, usando le parole del più recente e geniale personaggio di Woody Allen, anche perseguendo il “basta che funzioni”.

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.