Dokaz da je P!=NP

• 0Niko još nije pohvalio poruku.
  Registruj se da bi pohvalio/la poruku!

Jedan od nekoliko ( mislim 7 ) problema u racunarstvu izgleda ce biti resen(dokazan). Nagrada za bilo koje od tih pitanja je milion dolara.

Ukratko, u klasu P problema, spadaju problemi koji se mogu resiti u polinomijalnom vremenu. U NP klasu, spadaju teski problemi za koje se veruje da ne postoji algoritam polinomijalne slozenosti ali ciji se rezultat moze proveriti(potvrditi) u polinomijalnom vremenu.
Vise o samom problemu:
http://en.wikipedia.org/wiki/P_versus_NP_problem

Vise o dokazu(odnosno, vise o onome koje otkrio dokaz, nije jos uvek potvrdjeno da li je dokaz u redu ili ne) :
http://www.i-programmer.info/news/112-theory/1150-.....to-np.html

• 0Niko još nije pohvalio poruku.
  Registruj se da bi pohvalio/la poruku!

Citat:The proof has been reviewed publicly by academics,[22] and it was found to contain errors on a conceptual level, that cannot be repaired, as well as a number of concrete errors and flaws. The most notable comment was made by Terence Tao, claiming that there are fatal flaws in the proof.[23]

Vec su ga odbili

http://en.wikipedia.org/wiki/P_versus_NP_problem#Claimed_solutions