fbpx Sapere se un problema è difficile è un problema difficile | Scienza in rete

Sapere se un problema è difficile è un problema difficile

Primary tabs

Read time: 3 mins

Il 9 agosto scorso Vinoy Deolalikar, Principal Research Scientist in HP, ha reso pubblico il suo tentativo di dimostrare la congettura “P è uguale a NP?”, formalizzata da Stephen Cook nel 1970.  Per chi non lo sapesse, si tratta di una sorta di sacro Graal della scienza, un “Millenium Problem” per la soluzione dei quali il Clay Mathematical Institute ha messo in palio 1 milione di dollari. La congettura, ormai una splendida quarantenne, siede beatamente al centro della teoria della complessità computazionale e non cede facilmente alle blandizie degli scienziati, racchiudendo un quesito di grandissima rilevanza teorica e pratica.

Immaginiamo infatti di avere un problema e di cercarne la soluzione, e che questo problema possa essere descritto da un certo volume di informazioni, che chiameremo la dimensione del problema. La classe NP è composta dai problemi per i quali si può verificare che una certa risposta sia la soluzione che cerchiamo, in un tempo ragionevole, ovvero in un tempo che non cresce troppo velocemente al crescere della dimensione del problema. La classe P è composta dai problemi per i quali si è in grado anche di trovare la soluzione in un tempo ragionevole. P = NP implicherebbe che ogni problema in NP possa essere risolto in tempo ragionevole; viceversa, dovrebbe esistere almeno un problema in NP che non gode di questa proprietà.

Sebbene la questione possa sembrare squisitamente teorica, la dimostrazione della congettura avrebbe delle conseguenze pratiche molto rilevanti. Problemi di decisione o di ottimizzazione nella classe NP sono frequenti in molti settori di grande interesse economico e sociale – fra cui la logistica, la produzione, la crittografia. La dimostrazione della congettura avrebbe ricadute immediate nel mondo della tecnologia e della produzione, rendendo possibile sapere se una soluzione di un certo problema è veramente la migliore, o se è meglio cercarne un’altra.

Vinoy sostiene che P è diverso da NP, e quindi che i problemi veramente difficili esistono, eccome. Ma per avere una risposta definitiva sulla validità delle 100 pagine di dimostrazione bisognerà avere un po’ di pazienza. Il suo lavoro impiega raffinati strumenti matematici, ma alcuni autorevoli colleghi hanno già avanzato dubbi su alcuni passaggi (aggiornamenti in tempo reali sul blog di di Dick Lipton); il fervido ricercatore della HP può consolarsi ricordando che, se anche si dovesse scoprire qualche baco nella sua dimostrazione, sarebbe in buona compagnia. Come riporta il sito The_P_versus-NP_page, dal 1996 ad oggi sono stati proposte 30 dimostrazioni di P = NP e 24 del suo esatto contrario,  ma nessuna di queste è stata accettata dalla comunità scientifica. Una operazione utile l’ha fatta comunque William Gasarch (University of Maryland) nel 2002: abbandonando il formalismo matematico, ha intervistato 100 esperti di complessità,  che hanno volentieri espresso la loro opinione senza doversi preoccupare, una volta tanto, di fornire una prova formale delle loro affermazioni… così si scopre che quasi i due terzi del prezioso campione ritiene che la congettura sarà risolta prima del 2070, mentre il restante terzo pensa di dover aspettare ben di più; ma, indipendentemente dal tempo necessario, 61 dei 100 esperti ritengono che sarà risolta in senso negativo, ovvero che si dimostrerà che P è diverso da NP.

Per il momento, accontentiamoci: secondo il sondaggio, la cosa più probabile è che tra qualche decennio sapremo che P è diverso da NP, ma se il Dr. Deolalikar non ha fatto errori irreparabili nella sua dimostrazione, vorrà dire che ci siamo portati un po’ avanti. Nel frattempo, the show must go on: mentre voi leggete questo articolo, migliaia di ricercatori in tutto il mondo cercano disperatamente il modo per risolvere problemi difficili con algoritmi sempre più veloci, computer sempre più potenti, con soluzioni sempre migliori, senza potersi permettere il lusso di aspettare la dimostrazione della famosa congettura.


Scienza in rete è un giornale senza pubblicità e aperto a tutti per garantire l’indipendenza dell’informazione e il diritto universale alla cittadinanza scientifica. Contribuisci a dar voce alla ricerca sostenendo Scienza in rete. In questo modo, potrai entrare a far parte della nostra comunità e condividere il nostro percorso. Clicca sul pulsante e scegli liberamente quanto donare! Anche una piccola somma è importante. Se vuoi fare una donazione ricorrente, ci consenti di programmare meglio il nostro lavoro e resti comunque libero di interromperla quando credi.


prossimo articolo

Dieci anni dall'Accordo di Parigi, si può fare di più

A 10 anni di distanza dall’Accordo di Parigi, il bicchiere è mezzo pieno o mezzo vuoto? Nell’ultimo decennio sono stati compiuti progressi sostanziali: diversi Paesi hanno avviato una graduale decarbonizzazione, mentre Stati e aziende hanno moltiplicato gli impegni Net Zero. L’Unione Europea ha lanciato il pacchetto “Fit for 55” e fino a tempi recenti procedeva in linea con gli obiettivi fissati. È cresciuta anche l’attenzione agli effetti della crisi climatica sulla salute, riconosciuta come tema centrale già a partire dalla COP27, insieme alla necessità di collegare l’azione per il clima ai benefici locali. Ma le politiche attuali sono ancora insufficienti a raggiungere l’obiettivo di mitigazione dell’Accordo di Parigi, anche volendo tener conto di impegni futuri espressi spesso in modo vago e poco trasparente. In questo articolo gli autori analizzano le principali lacune nell’azione climatica internazionale e le questioni ancora aperte sulla priorità e la fattibilità delle diverse strategie di mitigazione, con un’attenzione specifica ai loro impatti sulla salute. 

Con l’Accordo di Parigi (dicembre 2015), i Paesi si sono impegnati a elaborare i propri piani di riduzione delle emissioni di gas serra, noti come Contributi determinati a livello nazionale (NDC). Nel loro insieme, questi impegni  non bastano a garantire nemmeno l’obiettivo minimo dell’Accordo di Parigi: avere una probabilità del 66% di restare sotto i 2 °C di riscaldamento entro la fine del secolo.