P!=NP

[•S7012MY]

am gasit pe internet documentul scribd.com/mobile/documents/35539144 asta in care se pare ca se afla demonstratia ca problemele NP complete nu pot fi rezolvate in timp polinomial. Probabil va mai dura pana va fi verificat.

[•azotlichid]

In fiecare an apar zeci de astfel de articole care pretind ca ar fi rezolvat P vs NP.
Interesant e ca asta este prima data cand cel care face public un astfel de articol se bucura si de un oarecare prestigiu in comunitatea cercetatorilor. Pentru moment stim ca si demonstratia sa contine greseli. Partea buna e ca ne ofera un framework nou care ar putea fi utilizat in viitor.
O serie de discutii foarte utile despre articolul lui Deolalikar a avut loc pe blogul lui Richard Lipton http://rjlipton.wordpress.com/. Multi din cei care posteaza acolo sunt destul de cunoscuti si cred ca e interesant sa urmaresti discutiile si sa vezi care mai sunt problemele fierbinti in theoretical cs.

Spor!

[•S7012MY]

am citit si eu ca contine greseli dar zicea ca o sa puna in weekendul asta o varianta finala. Parca astea is numai ciornele lui.