Problema Mileniului P≠NP este rezolvată?

Vinay Deolalikar, matematician indian şi cercetător în Matematica Aplicată la HP Labs, Paolo Alto, California, crede că a rezolvat enigma P≠NP, care este una dintre cel şapte Probleme ale Mileniului, pentru soluţionarea căreia Institutul de Matematică Clay oferă un premiu de un milion de dolari SUA, problema fiind clasificată ca ce mai dificilă dintre toate problemele mileniului.

Reamintim că într-o explicaţie simplistă, problemele din clasa P se rezolvă simplu, prin algoritmi de complexitate polinomială. Ordonarea unei liste în ordine alfabetică este un exemplu concludent pentru problemele de tip P.

Pentru problemele din clasa NP se verifică uşor soluţia (dacă e cunoscută), prin algoritmi de complexitate polinomială, dar însăşi complexitatea problemei de determinare a soluţiei rămânea o enigmă – polinomială sau exponenţială? Un exemplu concludent de problemă din clasa NP poate servi puzzle-ul! Aranjarea pieselor mozaicului este dificilă, iar verificarea corectitudinii rezultatului este deja simplă.

Înainte de formularea în mod independent a problemei în 1971 de către Stephen Cook şi Leonid Levin, matematicienii credeau ca aceste clase de probleme nu sunt egale, dar o demonstraţie a inegalităţii nu putea fi găsită.

Vinay Deolalikar a publicat demonstraţia sa de 100 de pagini on-line, iar pe 6 august, într-un e-mail către ai săi „fellow researchers”, Vinay Deolalikar a scris: „This work was pursued independently of my duties as a HP Labs researcher, and without the knowledge of others. I made several unsuccessful attempts these past two years trying other combinations of ideas before I began this work.” („Această lucrare a fost realizată în afara obligaţiunilor mele de serviciu ca cercetător la HP Labs şi fără ca alţii să ştie de ea. Am avut câteva încercări nereuşite în ultimii doi ani, testând alte combinaţii de idei până am început această lucrare”.)

Articolul urmează a fi publicat într-o revistă serioasă de specialitate şi rezultatele să fie aprobate de către comunitatea matematică în următorii doi ani. Preliminar, experţii consideră că este o lucrare care merită să fie serios studiată, iar Stephen Cook, căruia îi aparţine enunţul oficial al problemei, a numit lucrarea „o pretenţie relativ serioasă ca problema P=NP să fie rezolvată” („a relatively serious claim to have solved P vs NP”).

Mulţi au încercat să rezolve problema P=NP. Încercări de demonstraţie atât pentru P=NP, cât şi pentru P ≠ NP, au fost numeroase. O cronologie a pseudo-demonstraţiilor, precum şi a respingerii lor, poate fi consultată pe adresa:

http://www.win.tue.nl/~gwoegi/P-versus-NP.htm

Tot pe această adresă poate fi descărcat textul integral al articolului „P ≠ NP” al lui Vinay Deolalikar. Experţii remarcă că este o abordare total nouă, cum nu s-a mai întâlnit până acum.

Pe blogurile matematice au început să fie publicate deja analize riguroase ale demonstraţiei. Este evident că lucrarea mai are lacune şi greşeli, dar este important ca ele să poată fi depăşite, iar strategia demonstraţiei să fie corectă.

Dacă demonstraţia va fi corectă, atunci  Vinay Deolalikar are şansa să devină al doilea laureat al Premiului Mileniului de un milion de dolari SUA, premiu oferit de Institutul de Matematică Clay. Despre primul laureat – Grigory Perelman, am scris anterior.

În cazul în care demonstraţia se va adeveri, ea va avea un impact enorm şi în matematică, şi  în Informatică, şi în evoluţia de mai departe a  calculatoarelor.

Anunțuri

Un comentariu la “Problema Mileniului P≠NP este rezolvată?

  1. Pingback: Problema mileniului P≠NP este rezolvată? - Ziarul toateBlogurile.ro

Lasă un răspuns

Completează mai jos detaliile tale sau dă clic pe un icon pentru a te autentifica:

Logo WordPress.com

Comentezi folosind contul tău WordPress.com. Dezautentificare / Schimbă )

Poză Twitter

Comentezi folosind contul tău Twitter. Dezautentificare / Schimbă )

Fotografie Facebook

Comentezi folosind contul tău Facebook. Dezautentificare / Schimbă )

Fotografie Google+

Comentezi folosind contul tău Google+. Dezautentificare / Schimbă )

Conectare la %s