Questo prof avrebbe risolto uno dei problemi più complessi della matematica

Che cosa hanno in comune scoprire la cura per il cancro, organizzare una forma di capitalismo equo e la partita perfetta di Super Mario Bros.? Secondo una teoria matematica, trovare la soluzione a uno di questi problemi ci consentirebbe di risolvere in poco tempo anche tutti gli altri. Tutto ciò di cui abbiamo bisogno è di individuare un algoritmo più efficiente per dimostrare che problemi complessi — come il ripiegamento delle proteine, lo studio dell'efficienza dei mercati e l'analisi combinatoria — sono solo varianti di problemi più semplici che i supercomputer sono già in grado di risolvere.

Ma come può un singolo algoritmo semplificare problemi estremamente complessi? La risposta dipende da un'altra domanda: forse i problemi complessi sono solo dei problemi più semplici sotto mentite spoglie? Questo enigma rimane una delle più grandi questioni irrisolte della matematica moderna oltre ad essere uno dei sette problemi del Millennium Prize Problems. Ogni risposta che viene dimostrata come valida viene premiata con un milione di dollari.

Ora, un professore tedesco di nome Norbert Blum ha affermato di aver risolto l'enigma di cui sopra, noto come il problema P contro NP. Purtroppo, la soluzione da lui proposta non comporta buone notizie. Blum, dell'Università di Bonn, afferma nel suo paper di 38 pagine di recente pubblicazione che P non è uguale a NP. In altre parole, i problemi complessi sono fondamentalmente diversi da quelli semplici e non sembra che neanche i nostri computer più potenti possano risolverli nel prossimo futuro. Da quando il suo paper è stato pubblicato, numerosi matematici hanno cominciato a domandarsi se Blum abbia effettivamente risolto il problema.

La maggior parte degli informatici tende a concordare con la conclusione di Blum. I problemi complessi sono difficili da risolvere, quelli semplici sono facili da risolvere.

Nell'informatica, i problemi semplici spesso rientrano nell'insieme denominato P. Ciò significa che possono essere risolti in un "tempo polinomiale", praticamente in un lasso di tempo ragionevole. Molto più difficili sono i problemi raggruppati in NP, che i computer non sono in grado di risolvere in un periodo di tempo ragionevole. Quindi, dal punto di vista pratico, i problemi di NP possono essere considerati non risolvibili dai computer. (Si noti che NP sta per "tempo polinomiale non deterministico" anziché "tempo non polinomiale").

Ecco qualche esempio di problemi NP:

Il ripiegamento delle proteine: il processo attraverso il quale le proteine di un organismo ottengono la loro struttura tridimensionale. Una migliore comprensione di questo processo potrebbe aiutarci a riconoscere o addirittura prevenire le mutazioni, il che potrebbe anche curare alcune forme di cancro.

L'individuazione di un itinerario: come calcolare un percorso di viaggio ottimizzato in 15 città diverse senza passare per la stessa città due volte? Un problema complesso da risolvere anche per un supercomputer, ecco perché, in informatica, anche questo viene considerato un problema NP.

La partita perfetta di scacchi: una partita di scacchi prevede un numero infinito di mosse possibili, tale che persino un supercomputer dotati di un'incredibile capacità di calcolo non può determinare la tattica perfetta per vincere. Molti matematici considerano questo problema talmente difficile che non lo considerano neanche un problema NP, reputandolo direttamente al di fuori del campo di possibilità di risoluzione.

Tutti questi problemi complessi hanno una cosa comune: se trovare una soluzione ai problemi di NP è complicato, d'altro canto, risulta relativamente facile controllare la validità delle soluzioni una volta trovate.

Queste due distinzioni categoriche nella complessità dei problemi hanno avuto origine prima della diffusione dei personal computer. Negli anni Settanta, quando i computer erano ancora delle dimensioni di un frigo, si decise rapidamente che non tutti i problemi dell'umanità potevano essere semplicemente risolti da quelle macchine. Per questo, è stato proposto che la distinzione venisse formalizzata in termini di complessità computazionale, portando ad una serie di classi di complessità, tra cui N e NP.

A partire dalla definizione formale di P e NP nel 1971, gli informatici hanno discusso se fosse possibile elaborare un algoritmo in grado di ridurre o ridefinire i problemi di NP in modo da risolverli in un tempo polinomiale. Se qualcuno riuscisse a dimostrare che tutti i problemi di NP sono solo delle variazioni dei problemi P, allora tutti i problemi di NP sarebbero soggetti alla stessa forma di riduzione. In altre parole, chiunque scopra la tattica per giocare la partita perfetta di Super Mario Bros. potrebbe curare anche il cancro.

In totale, 116 degli studiosi più arditi delle loro rispettive discipline hanno tentato ufficialmente di risolvere questo mistero (anche se molti informatici hanno pubblicato sedicenti soluzioni su messageboards e siti come arXiv). Finora nessuna di queste prove è stata riconosciuta ufficialmente dalla comunità matematica.

Nel 2000, il Clay Mathematics Institute (CMI) di Oxford ha compilato una lista di sette problemi non ancora risolti instituendo il Millennium Prize Problems, il quale assegna un milione di dollari a chi risolve i problemi, come una sorta di Chi vuole essere milionario? per matematici.

I problemi del Millennium Prize Problems sono considerati eccezionalmente difficili da risolvere anche dagli esperti. Solo per comprendere le domande, sono necessarie una grande quantità di conoscenze specifiche. L'unico problema della lista che finora è stato risolto è la congettura di Poincaré, un problema non semplice da spiegare in poche parole in un articolo dedicato principalmente ad un altro argomento già complesso di per sé.

La risoluzione del problema NP, tuttavia, non avrebbe conseguenze del tutto positive. Ad esempio, la maggior parte della crittografia si basa sulla difficoltà di fattorizzare numeri primi molto grandi. La fattorizzazione dei numeri interi è un problema appartenente alla classe NP. Un codice a 256 bit, come quelli utilizzati dalle istituzioni finanziarie nei pagamenti online con carta di credito, è considerato molto sicuro. Se qualcuno dimostrasse che NP è equivalente a P, le banche dovrebbero trovare in poco tempo un metodo di sicurezza diverso.

Dal quando il paper di Blum è stato pubblicato, i matematici e gli informatici di tutto il mondo si sono messi all'opera per determinare se il ricercatore abbia effettivamente risolto questo problema del Millennium Prize Problem. Dopo una reazione iniziale positiva, come quella del matematico di Stanford Reza Zadeh, sono iniziati ad emergere dubbi circa il corretto ragionamento di Blum.

In un forum dedicato alla matematica teorica, un utente di nome Mikhail ha contatto Alexander Razborov — l'autore del paper su cui si basa la prova di Blum — per chiedergli del documento di Blum. Razborov sostiene di aver scoperto un errore nel documento di Blum: l'argomento principale di Blum contraddice una delle ipotesi chiave di Razborov. E il matematico Scott Aaronson, un'autorità nella comunità matematica per quanto riguarda P vs NP, ha dichiarato di essere disposto a scommettere 200.000 dollari che la prova matematica di Blum non regge.

"Per favore smettete di chiedermelo," scrive Aaronson. Se la prova non viene confutata, "potete tornare qui e dirmi che sono stato uno stupido".

Nella settimana successiva alla pubblicazione del post iniziale di Aaronson, altri matematici hanno tentato di trovare dei difetti nella prova di Blum. Dick Lipton, professore di informatica della Georgia Tech, ha scritto in un post sul blog che la prova di Blum "passa molti test," ma ha suggerito che ci potrebbero essere dei problemi. Un commentatore del post, firmatosi come "vloodin", ha osservato che nella prova è contenuto un "errore su un punto molto specifico." Altri matematici hanno confermato l'analisi iniziale di vloodin, e quindi l'opinione emergente tra molti matematici è che P contro NP rimanga irrisolvibile.