Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.

Problem P vs NP opet napadnut

[es] :: Matematika :: Problem P vs NP opet napadnut

[ Pregleda: 2531 | Odgovora: 7 ] > FB > Twit

Postavi temu Odgovori

Autor

Pretraga teme: Traži
Markiranje Štampanje RSS

holononi

Član broj: 163572
Poruke: 658
*.adsl.verat.net.



+5 Profil

icon Problem P vs NP opet napadnut10.08.2010. u 15:05 - pre 166 meseci
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.
 
Odgovor na temu

Fratello

Član broj: 267386
Poruke: 7
*.access.telenet.be.



+1 Profil

icon Re: Problem P vs NP opet napadnut01.09.2010. u 18:26 - pre 165 meseci
Bice da i ovog puta od tog posla nema nista :)
 
Odgovor na temu

holononi

Član broj: 163572
Poruke: 658
*.dynamic.isp.telekom.rs.



+5 Profil

icon Re: Problem P vs NP opet napadnut01.09.2010. u 18:41 - pre 165 meseci
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.
 
Odgovor na temu

Fratello

Član broj: 267386
Poruke: 7
*.access.telenet.be.



+1 Profil

icon Re: Problem P vs NP opet napadnut01.09.2010. u 19:01 - pre 165 meseci
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.
 
Odgovor na temu

petarm
Petar Mali
Zrenjanin

Član broj: 20220
Poruke: 1879
*.dynamic.sbb.rs.



+33 Profil

icon Re: Problem P vs NP opet napadnut02.09.2010. u 14:58 - pre 165 meseci
Bilo bi lepo da neko napise nesto vise o ovom problemu!
 
Odgovor na temu

boxxter

Član broj: 189779
Poruke: 710
216.66.59.*



+21 Profil

icon Re: Problem P vs NP opet napadnut07.09.2010. u 22:29 - pre 165 meseci
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/

Prikačeni fajlovi
 
Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8632
212.200.65.*



+2789 Profil

icon Re: Problem P vs NP opet napadnut07.09.2010. u 23:03 - pre 165 meseci
Citat:
petarm: Bilo bi lepo da neko napise nesto vise o ovom problemu!


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.
Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.
 
Odgovor na temu

holononi

Član broj: 163572
Poruke: 658
..-100-1.static.steadfast.net.



+5 Profil

icon Re: Problem P vs NP opet napadnut08.09.2010. u 15:31 - pre 165 meseci
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.
 
Odgovor na temu

[es] :: Matematika :: Problem P vs NP opet napadnut

[ Pregleda: 2531 | Odgovora: 7 ] > FB > Twit

Postavi temu Odgovori

Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.