neprihlásený Sobota, 4. decembra 2021, dnes má meniny Barbora
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:
                               
 

Toto nikdy nenastane. To ze je algoritmus exponencialny znamena, ze cas potrebny pre jeho vypocitanie sa zvysuje OMNOHO rychlejsie, ako polynomialny. Vobec to neznamena, ze ten polynomialny je za kazdych okolnosti rychlejsi...

Pre jednoduchost sa to da vysvetlit ako ze polynomialny algoritmus je stihacka a exponencialny algoritmus je bezec. Ale ked bezec ma prejst 10m vzdialenost, tak to stihne rychlejsie ako stihacka, ktoru treba pred startom skontrolovat ci funguje, nastartovat a podobne...

Ale ked uz sa ma prejst 1000km, tak uz to ta stihacka stihne asi o nieco rychlejsie a je jedno, ze si tych bezcov postavil na trat 10 (to by mohol predstavovat ten tvoj pokrok a zvysenie vypoctu pocitacov), ktory si ten usek rovnocenne medzi sebou podelia...

No a v reali je ten rozdiel dokonca este vecsi...

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".