P è uguale a NP? Secondo il ricercatore Vinay Deolalikar la risposta definitiva è no.
Per chi non ha conoscenze di complessità computazionale:
In questa teoria, la classe P consiste di tutti quei problemi di decisione che possono essere risolti con una macchina sequenziale deterministica in un tempo che è polinomiale rispetto alla dimensione dei dati di ingresso; la classe NP consiste di tutti quei problemi di decisione le cui soluzioni positive possono essere verificate in tempo polinomiale avendo le giuste informazioni, o equivalentemente, la cui soluzione può essere trovata in tempo polinomiale con una macchina non deterministica.
Un problema che espresso in questo modo può sembrare particolarmente contorto per i profani, ma che ha un’importanza talmente vasta da essere entrato a far parte dei 7 problemi matematici del millennio, un grande dilemma dell’informatica teorica.
I primi commenti sulla qualità della dimostrazione, un documento da un centinaio di pagine, parlano di una ricerca solida che potrebbe essere la soluzione cercata da molti. Per le persone normali non cambierà molto, ma finalmente possiamo avere la certezza che esistono dei problemi che si possono calcolare solo in tempi non deterministici, ma verificare in tempi polinomiali. Le fondamenta della crittografia.
Foto | Wikipedia
Via | GregBaker
ossblog è un supplemento alla testata Blogo.it registrata presso il Tribunale di Milano n. 487/06, P. IVA 04699900967. Contatti, chi siamo
© 2004-2011 Blogo.it, alcuni diritti riservati sotto licenza Creative Commons.
Per informazioni pubblicitarie e progetti speciali su Ossblog.it contattare la concessionaria esclusiva Populis Engage.
alebaffa
09 ago 2010 - 13:22 - #1studiati all’universitá in corsi come Ricerca Operativa o Algebra e Logica Matematica. Inutile dire che sto male solo a ripensarci …
Anonimo codardo
09 ago 2010 - 13:28 - #2Magari diciamolo che è un documento che non è stato sottoposto ad alcun tipo di peer review…
Fabiooo
09 ago 2010 - 13:36 - #3Per il teorema di Rais, mo bestemmio :D:D:D
nondiciamostupidate
09 ago 2010 - 13:46 - #4Dell’ultimo tearema di ferma erano in molti a credere che fosse vero, ma ci sono voluti 350 anni ed una dimostrazione rigorosa di circa 200 pagine. Aspettiamo la pubblicazione e la formale accettazione della dimostrazione.
PD
09 ago 2010 - 14:46 - #5Se questo tizio è davvero riuscito a fornire una dimostrazione valida, verrà praticamente ricoperto di soldi, beato lui :D
@alebaffa
Dai, c’è decisamente di peggio…
UsqueTandem?
09 ago 2010 - 15:14 - #6@nondiciamostupidate
Scusa, mi sfugge il link tra ultimo teorema di Fermat e problemi classe LP.
(premesso che per per dimostrare l’uno si usano le matrici e per l’altro la modellazione con grafi).
nondiciamostupidate
09 ago 2010 - 15:18 - #7x UsqueTandem?
scusa non sono stato chiaro.
Il parallelo tra fermat e P = NP era relativamente ai tempi di dimostrazione e non altro.
Intendevo dire che tra l’enunciazione di Fermat alla sua effettiva di dimostrazione sono passati circa 350 anni, quindi per la dimostrazione o confutazione di P = NP potrebbero passare moti anni ed inoltre la dimostrazione deve essere accettata universalmente.
UsqueTandem?
09 ago 2010 - 15:22 - #8@nondiciamostupidate
…..accettando il tuo principio dovrei dare al tuo nick la stessa semantica che ha la parola GNU.
aytin
09 ago 2010 - 21:28 - #9NP, NP-Completo, NP-Arduo… che nostalgia
Luca Bruno
10 ago 2010 - 11:03 - #10Ma non mettete mai il link utile a quello di cui si parla. Mai un link ad una homepage, mai un link all’articolo esterno.
michele_
10 ago 2010 - 17:08 - #11Da Wikipedia non è stata presa solo la foto! Ma il 80% dell’articolo.
PS. L’ultima frase sulla crittografia è davvero avvilente.
Giorgio Camerani
31 ago 2010 - 16:27 - #12“I primi commenti sulla qualità della dimostrazione, un documento da un centinaio di pagine, parlano di una ricerca solida che potrebbe essere la soluzione cercata da molti”
Questa affermazione non coincide con la realtà. Ricercatori di fama mondiale (Terence Tao, Neil Immermann, Russell Impagliazzo, Scott Aaronson, Timothy Gowers) hanno evidenziato seri problemi in merito alla correttezza della dimostrazione. In attesa di una nuova versione della dimostrazione, il parere condiviso della comunità TCS (Theoretical Computer Science) è che l’attuale dimostrazione sia errata. I principali motivi sono i seguenti:
1. La caratterizzazione della classe P utilizzata da Deolalikar, mediante Finite Model Theory, non è sufficientemente espressiva. In altre parole essa non riesce a catturare la totalità degli algoritmi deterministici tempo polinomiali: tale caratterizzazione rappresenta quindi solo un sottoinsieme di tali algoritmi. Pertanto non può essere usata per separare P da NP.
2. Deolalikar utilizza la seguente assunzione: i problemi facili (quelli, cioè, risolubili efficientemente, vale a dire in tempo polinomiale) hanno spazi delle soluzioni facili, mentre i problemi difficili hanno spazi delle soluzioni difficili. Uno spazio delle soluzioni è detto essere facile se e solo se è rappresentabile mediante un numero polilogaritmico di parametri. In realtà, è stata fatta notare tanto l’esistenza di problemi efficientemente risolubili aventi spazi delle soluzioni difficili, quanto l’esistenza di problemi difficili aventi spazi delle soluzioni facili (a tal proposito, si pensi al fatto che il problema Unique-SAT è NP-Completo). L’opinione formatasi nella comunità è la seguente: qualunque strategia che si prefigga di separare P da NP mediante considerazioni sullo spazio delle soluzioni è destinata al fallimento.
Vedasi l’eccellente blog del Prof. Richard Jay Lipton (rjlipton.wordpress.com).
Luigi Salemi
15 set 2010 - 15:16 - #13Anche secondo me Deolalikar si sbaglia. Però sono di parte perché penso che P = NP, e forse sono sulla buona strada per provarlo. Se volete essere i primi a congratularvi con me (o semplicemente i primi a trovare il mio errore) l’indirizzo è questo www.visainformatica.it/3sat
Attendo critiche e obiezioni