P vs NP pre každého. Čo by znamenalo P != NP a čo P = NP


Diskusia k článku: P vs NP pre každého. Čo by znamenalo P != NP a čo P = NP

Prispievajte do diskusií ako prihlásený užívateľ.

Komentár, na ktorý odpovedáte:

Re: ...som asi za kopec... Od: Pjetro de | Pridané: 2010-08-18 07:52:49 T.j. ak zmenime pocet spracuvanych udajov z 25 na 50, tak pri linearnej zlozitosti nam pocet potrebnych krokov (no laicky povedzme ze aj potrebny cas vypoctu) stupne 2nasobne podobne ako pocet vstupnych dat. Podoha a relax. Pri kvavdatickej zlozitosti nam pocet potrebnych krokov stupne (50^2)/(25^2) = 25^2 = 625nasobne. To uz je blbe. No a pri exponencilnej zlozitosti zo zakladom 2 je to ciste svinstvo, tam totiz pri 2nasobnom zvyseni poctu spracuvaynch dat z 25 na 50 stupna pocet potrebnych krokov a teda aj caova narocnost az 33554432nasobne! Odpovedať

Meno:


Titulok:


Text:


Prihláste sa a povoľte si emailové notifikácie na odpovede na Váš príspevok.

Overovací text:



Pre overenie, že komentár sa nepridáva automatizovanými prostriedkami, prosím prepíšte text, ktorý vidíte na obrázku. Písmená musíte zadávať rovnako ako na obrázku veľké. Pokiaľ text neviete prečítať, kliknite prosím na tlačidlo "Obnoviť obrázok". V texte sa používajú iba znaky "BCDJKMPRSVWXY1234589".