Questo articolo è originariamente apparso su Motherboard Germany. Dalla sua pubblicazione originale è stato aggiornato con nuove informazioni da Motherboard US. Cosa hanno in comune il cancro curabile, il capitalismo equo e il gioco perfetto di Super Mario Bros.? Secondo una teoria matematica, la soluzione a uno qualsiasi di questi problemi ci permetterebbe di risolvere rapidamente gli altri., Tutto ciò che serve sono algoritmi migliori per dimostrare che domande complicate—come il ripiegamento delle proteine, mercati efficienti e analisi combinatorie-sono semplicemente variazioni di problemi più semplici che i supercomputer sono già in grado di risolvere. Ma come può un algoritmo semplificare problemi estremamente complicati? Questo dipende da un’altra domanda: cosa succede se i problemi complicati sono in realtà solo semplici problemi sotto mentite spoglie?, Questo enigma rimane una delle più grandi questioni irrisolte della matematica moderna, ed è uno dei sette problemi del Premio del Millennio, per i quali ogni risposta accettata viene premiata con un milione di dollari.
Ora, un uomo tedesco di nome Norbert Blum ha affermato di aver risolto l’enigma sopra, che è correttamente noto come problema P vs NP. Sfortunatamente, la sua presunta soluzione non porta buone notizie., Blum, che proviene dall’Università di Bonn, afferma nel suo articolo di 38 pagine pubblicato di recente che P non è uguale a NP. In altre parole, i problemi complicati sono fondamentalmente diversi dai problemi semplici e non sembra che i nostri computer ad alte prestazioni saranno in grado di risolvere questi problemi più difficili in qualsiasi momento nel prossimo futuro. E nei giorni da quando il suo articolo è stato pubblicato, numerosi matematici hanno iniziato a sollevare domande sul fatto che Blum lo abbia risolto del tutto.
Qual è esattamente il problema P rispetto a NP?,
La maggior parte degli informatici tende ad essere d’accordo con la conclusione di Blum. I problemi difficili sono difficili, i problemi facili sono facili. In informatica, i problemi facili di solito cadono sotto la bandiera di P. Ciò significa che possono essere risolti in “tempo polinomiale”, che è molto simile a dire che possono essere risolti in un periodo di tempo ragionevole. Molto più difficili sono i problemi NP, che i computer non sono in grado di risolvere in un lasso di tempo ragionevole. Per scopi pratici, i problemi NP potrebbero anche essere irrisolvibili dai computer., (Si noti, tuttavia, che NP sta per” tempo polinomiale non deterministico “piuttosto che” tempo non polinomiale”.) Ecco alcuni esempi di problemi NP:
Ripiegamento delle proteine: il processo attraverso il quale le proteine in un organismo biologico ottengono la loro struttura. Una migliore comprensione di questo processo potrebbe aiutarci a riconoscere o addirittura ostacolare le mutazioni, che potrebbero curare alcune forme di cancro. Routefinding ottimizzato: un percorso di viaggio ottimizzato attraverso 15 città diverse senza visitare la stessa città due volte?, Un dado duro da decifrare, anche per un supercomputer, motivo per cui questo è anche considerato un problema NP in informatica.
Il gioco degli scacchi perfetto: una partita a scacchi ha infinite mosse possibili, tali che anche un supercomputer con capacità incredibile non può determinare una tattica perfetta. Molti matematici considerano questo problema così difficile da non considerarlo un problema NP, ma piuttosto lo considerano completamente fuori dal regno delle possibilità.,
Tutti questi problemi complessi hanno una cosa in comune: per quanto difficile possa essere trovare una soluzione ai problemi NP, è relativamente facile verificare la validità delle soluzioni una volta che le hai.
Queste due distinzioni categoriali nella complessità dei problemi hanno origini prima dell’ascesa sociale dei computer domestici. Nel 1970, quando i computer erano ancora le dimensioni di un frigorifero goffo, è stato rapidamente determinato che non tutti i problemi dell’umanità potrebbero essere risolti semplicemente da quelle macchine., È stato proposto che la distinzione potrebbe essere formalizzata in termini di complessità computazionale, portando a una suite 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 sia possibile o meno trovare un algoritmo in grado di ridurre o ridefinire i problemi NP in modo tale che possano essere risolti in tempo polinomiale. Se qualcuno fosse in grado di dimostrare che tutti i problemi NP sono in definitiva solo variazioni di problemi P, allora tutti i problemi NP sarebbero essenzialmente soggetti alla stessa forma di riduzione., In altre parole, chiunque conosca la tattica perfetta di Super Mario Bros. potrebbe anche curare il cancro.
In totale, 116, i più coraggiosi nel loro campo hanno ufficialmente tentato di risolvere questo mistero (anche se untold più computer, gli scienziati hanno inviato sarebbero soluzioni per messageboards e su siti come arXiv). Ad oggi, nessuna di queste prove è stata ufficialmente riconosciuta dalla comunità matematica.
Una sorta di Chi vuole essere milionario?, per i matematici
Nel 2000, il Clay Mathematics Institute (CMI), con sede a Oxford, ha compilato una lista di sette problemi irrisolti del Millennium Prize, impegnando un milione di dollari per ogni soluzione. E ‘ una specie di Chi vuole essere milionario? o X Premio per matematici. I problemi del Premio del Millennio sono considerati eccezionalmente difficili anche negli ambienti esperti. Una ricchezza di conoscenze specifiche del campo è necessaria per comprendere anche le domande., L’unico problema del premio del millennio risolto fino ad oggi è la congettura di Poincaré, che non è facilmente spiegabile come parte in un articolo su un diverso concetto di matematica.
Risolvere il problema NP non sarebbe una cosa del tutto buona. Ad esempio, la maggior parte della crittografia si basa sulla difficoltà di factoring numeri primi molto grandi. La fattorizzazione intera è un problema NP di classe. Un codice a 256 bit, come quelli che le istituzioni finanziarie utilizzano nei pagamenti con carta di credito online, è considerato infrangibile e quindi molto sicuro., Se qualcuno dovesse dimostrare che NP è uguale a P, le banche dovrebbero trovare rapidamente un metodo di sicurezza diverso.
Cosa pensano i matematici della dimostrazione matematica di Blum?
Da quando è stato pubblicato il documento di Blum, matematici e informatici di tutto il mondo si sono tormentati sul fatto che il ricercatore di Bonn abbia effettivamente risolto questo problema del premio del Millennio. Dopo una reazione inizialmente positiva, come quella del matematico di Stanford Reza Zadeh, cominciano a sorgere dubbi sul fatto che il ragionamento di Blum sia corretto.,
In un forum per la matematica teorica, un utente di nome Mikhail ha contattato Alexander Razborov—l’autore del documento su cui si basa la prova di Blum—per chiedergli del documento di Blum. Razborov pretende 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, che è una sorta di autorità nella comunità matematica quando si tratta di P vs., NP, ha detto che sarebbe disposto a scommettere 2 200.000 che la prova matematica di Blum non durerà. “Per favore smettila di chiedere”, scrive Aaronson. Se la prova non è stata confutata, ” puoi tornare e dirmi che ero un pazzo dalla mente chiusa.”Nella settimana dal post iniziale sul blog di Aaronson, altri matematici hanno iniziato a cercare di fare buchi nella prova di Blum. Dick Lipton, professore di informatica presso Georgia Tech, ha scritto in un post sul blog che la prova di Blum “passa molti filtri di serietà”, ma ha suggerito che potrebbero esserci alcuni problemi con esso., Un commentatore su quel post sul blog, noto solo come” vloodin”, ha notato che c’era un” singolo errore su un punto sottile ” nella dimostrazione; altri matematici da allora sono intervenuti e hanno confermato l’analisi iniziale di vloodin, e quindi il consenso emergente tra molti matematici è che una soluzione per P vs. NP rimane sfuggente. Traduzione di Melina McCormack.