Forum Klix.ba

Posted: **09/08/2010 20:02**

Eno javljaju da si skontali Bermudski trougao, danas citam ovo...

Has Vinay Deolalikar really solved the p=!np mystery?

Vinay Deolalikar is today’s most popular web personality. Internet users are searching for this computer scientist and his recent accomplishment in the field of mathematics and computer sciences. Reportedly, Vinay Deolalikar is claiming that he’s found the proof that P=!NP.

He sent a manuscript on August 6, 2010 to different researchers of his field and claimed that it contains the proof that P is not equal to NP. In his manuscript, Vinay Deolalikar said that his proof has combined different principles of several parts of mathematics and has uncovered the conceptual links between different mathematical fields.

Vinay Deolalikar is claiming that he’s resolved a Millennium Prize Problem. P is not equal to NP is one of the seven Millennium Prize Problems which were presented by the Clay Mathematics Institute in 2000. If any scientist or institute provides a solution to any of these problems, he’ll be awarded with $1,000,000 prize by Clay institute.

If Vinay Deolalikar’s proof that P is not equal to NP is correct, then five problems will remain unresolved. Prior to Vinay Deolalikar, Grigori Perelman solved the Poincare Conjecture problem and received the Millennium Prize.

Claims are surfacing that Vinay Deolalikar’s proof is wrong but at the same time it’s being stated that his proof introduces the researchers to some thought-provoking ideas. Only time will tell if Vinay Deolalikar has really resolved a Millennium Prize Problem or not.

Vinay Deolalikar was born in India in 1971. He has received his engineering degree from IIT, Bombay and his PhD from University of Southern California. Deolalikar is currently working as the Principal Research Scientist at HP Labs.

Source: http://www.buzztab.com/latest-news/has- ... p-mystery/

Evo i manuskripta: http://www.win.tue.nl/~gwoegi/P-versus- ... alikar.pdf

Posted: **09/08/2010 20:06**

sta ba?
sta je P a sta je NP? mogu li dvije-tri recenice jednostavnim rijecima

Posted: **09/08/2010 20:12**

U dvije tri recenice... Tesko. Jer da je moguce skratit u dvije tri recenice, nebi bilo jedno od 7 pitanja milenija

Radi se o poznatom problemu iz polja teoretske informatike, problemu kompleksiteta algoritama za rijesavanje specijalnih problema.

Vise informacija na http://en.wikipedia.org/wiki/Complexity_class

Posted: **09/08/2010 20:23**

Ovaj problem je jedan od famoznih Milenijumskih problema u matematici. Za rjesavanje jednog od njih dobiva se nagrada od 1M €.
P i NP su dvije klase algoritama klasirane prema efikasnosti. P je polinomski efikasan algoritam, a NP je nedeterministicki polinomski efikasan algoritam. Pod pojmom efikasnosti se gleda koliko iteracija je algoritmu potrebno za N problemskih varijabli. Jedan od poznatih P problema je linearno programiranje.
NP problemi su drugaciji. Sama rijec u nazivu (nedeterministicki) govori da su to problemi koji mogu imati jednu ili vise "tacaka odabira" i za svaki algoritam trazi drugacije racunanje. Obicno je za razlicite probleme drugacija kompleksnost i obicno su to neke nelinearne funkcije koje nisu polinomi (mislim na dio odredjivanja stepena polinoma). Jedan od najpoznatijih je problem trgovackog putnika http://en.wikipedia.org/wiki/Traveling_salesman_problem.

Posted: **09/08/2010 20:26**

Hvala najljepsa na kratkom i jasnom pojasnjenju, odlican odgovor.

Forum Klix.ba

Misterija P != NP izgleda napokon rijesena

#1 Misterija P != NP izgleda napokon rijesena

#2 Re: Misterija P != NP izgleda napokon rijesena

#3 Re: Misterija P != NP izgleda napokon rijesena

#4 Re: Misterija P != NP izgleda napokon rijesena

#5 Re: Misterija P != NP izgleda napokon rijesena