A quanto pare qualcuno ha la prova che P != NP. Questo qualcuno è Vinay Deolalikar (insieme ad un team di matematici), Principal Research Scientist presso gli HP Labs di Palo Alto.La notizia ha iniziato a circolare grazie ad una mail, parzialmente pubblicata da Greg Baker: http://gregbaker.ca/blog/2010/08/07/p-n-np/.
Successivamente è stata ripresa qui:
- http://science.slashdot.org/story/10/08/08/226227/Claimed-Proof-That-P--NP
- http://www.allvoices.com/contributed-news/6477443-vinay-deolalikar-has-claimed-to-solve-the-biggest-dilemma-of-the-century.
articolo del 6 agosto e articolo del 9 agosto.
Leggendo le varie notizie online Vinay Deolalikar sembra essere uno scienziato conosciuto nel settore, quindi l'articolo sembrerebbe una cosa seria. Tuttavia, ovviamente, le oltre 100 pagine del paper devono essere ancora controllare da altri esperti. Non mancano i commenti più o meno completi e critici, per esempio questi sul blog di Dick Lipton (Professor of Computer Science at Georgia Tech):
http://rjlipton.wordpress.com/
http://rjlipton.wordpress.com/2010/08/08/a-proof-that-p-is-not-equal-to-np/.
Il problema P versus NP è uno dei sette Millennium Prize Problems e, ammesso che la dimostazione sia corretta, sarebbe il secondo fra i problemi risolti, dopo la congettura di Poincaré dimostrata da Grigori Perelman nel 2003.
Per una sintesi del problema:
http://it.wikipedia.org/wiki/Complessit%C3%A0_P_e_NP.
Per una visione più avanzata:
http://en.wikipedia.org/wiki/P_versus_NP_problem
http://www.claymath.org/millennium/P_vs_NP/.
cercando deolalikar su google sei il terzo risultato!! quante probabilità c'erano??:-)
ReplyDeleteGabryzen :-)
eheh infatti! :)
ReplyDeleteMisteri di Google!
Abbastanza certo che sia l'ennesimo fallimento. Di scienziati che affermano di aver risolto il problema ce ne sono a decine ogni giorno. Vedremo!
ReplyDeleteC'è qualcuno di buona volontà disposto a guardare il mio tentativo di P = NP su www.visainformatica.it/3sat?
ReplyDeleteSe sono l'ennepiùunesimo fallimento pazienza.
@Luigi Salemi
ReplyDeleteCiao! Non sono un esperto del settore e mi perdo facilmente.
Tuttavia so che in università praticamente tutti tendono verso P!=NP.
In ogni caso, perchè non proponi il tuo lavoro ad un prof universitario di Ricerca Operativa?
Sono 2 gli orientamenti prevalenti: P verso NP è una questione difficile; la risposta più probabile è che P != NP.
ReplyDeleteUna piccola parte la pensa diversamente: P = NP e si può costruire una soluzione ad uno dei problemi NP Hard.
E' ciò che ho provato a fare, qualcuno la sta guardando e non mi sono ancora arrivate segnalazioni di errori. Il dissenso arriva presto, il consenso impiega più tempo, questo ritardo mi rende moderatamente ottimista.
Ciao.