neprihlásený Streda, 1. decembra 2021, dnes má meniny Edmund
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:
                               
 

Pokusim sa trocha poludstit: polynomialny algoritmus moze ten problem vypocitat rychlejsie pre nejaky velmi velky vstup.
Co je nam to ale platne, ked taky velky vstup v praxi nemusime nikdy potrebovat...
Ci nastane tento efekt, kedy je exponencialny algoritmus v praxi vyhodnejsi zalezi od:
1, velkosti vstupnych dat
2, ako male su koeficienty v exponenialnom algoritme
3, aky velky je stupen polynomu
4, ako velke su koeficienty v polynomialnom algoritme

Zhrnute dokopy na priklade:
Majme vstup o 10 prvkov.
Exponencialny algoritmus 2^N (kde N predstavuje pocet prvkov na vstupe = u nas 10).
Polynomialny algoritmus N^4

V tomto pripade exponencialny algoritmus musi vykonat 2^10=1 024 operacii.
Polynomialny 10^4=10 000 operacii. Polynomialny algoritmus by teda isiel dlhsie.
Pri zvecseni vstupu na N=20 nam da polynomialny algoritmus 160 000 operacii ALE exponencialny dava 1 048 576 operacii...

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