Problem P vs NP opet napadnut

Vinay Deolalikar (http://www.hpl.hp.com/personal/Vinay_Deolalikar/), istraživač zaposlen u HP labs je objavio svoj rad u kome dokazuje

P != NP

Rad (http://www.hpl.hp.com/personal...lalikar/Papers/pnp_updated.pdf) je objavljen 6. avgusta 2010. i povremeno se dopunjuje.

Bice da i ovog puta od tog posla nema nista :)

Autor dokaza još uvek radi na tome. Umesto kompletnog dokumenta na sajtu je sada samo skraćen sinopis (http://www.hpl.hp.com/personal...alikar/Papers/pnp_synopsis.pdf). Po rečima autora dobio je odredjen broj povratnih informacjia i objaviće novi dokument koji je u pripremi.

Bilo je svakakvih reakcija. Jedan profesor, uveren da resenje nije tacno, mu je ponudio cak svojih 200.000 dolara ukoliko zaradi milion. Da ne filozofiram mnogo, koga interesuje, ima, na primer, i ovde nesto o tome.

Bilo bi lepo da neko napise nesto vise o ovom problemu!

Potpis

http://www.svijetfizike.com/

Interesantna stvar sa linka koji je holononi postavio.

Self-study notes on some areas in Logic:

* Elementary Equivalence, Partial Isomorphism, and Scott-Karp analysis (self-study notes)

http://www.hpl.hp.com/personal/Vinay_Deolalikar/

Pa, P=NP je ekvivalentno sa postojanjem programa P i polinoma p takvih da za ma koju iskaznu formulu sa n iskaznih slova datu kao ulaz u program P, program se zaustavlja u ne više od p(n) koraka i na izlazu daje 1 ako je formula na ulazu tautologija, a 0 u suprotnom.

Potpis

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

P vs NP se može jednostavno opisati kao problem da li postoji pitanje čiji odgovor može biti brzo proveren, ali koji zahteva nemoguće dugo vremena da bi se rešilo bilo kojom direktnom procedurom. Pogledati na primer http://www.claymath.org/millennium/P_vs_NP/).

Stephen Cook i Leonid Levin su formulisali P (t.j., lako za pronaći) vs NP (t.j., lako za proveriti) problem nezavisno 1971. god.

U knjizi M. 2ivkovića “Agoritmi” ćete takodje pronaći pojednostavljenu formulaciju tog problema pa vam može poslužiti za uvod uz napomenu da je materija tako izložena da morate biti upoznati sa pojmovima kao što su složenost algoritma, Tjuringova mašina, deterministička Tjuringova mašina i slično.