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:
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
comment
Od: Pjetro de
|
Pridané:
2010-08-17 19:21:37
Ani polynomiálny algoritmus zároveň nemusí zabezpečiť pre vstupy, pre ktoré sa jednotlivé problémy bežne počítajú, rýchlejší výpočet ako umožňujú súčasné algoritmicky menej optimálne nepolynomiálne algoritmy. Stupeň polynómu, koeficienty a tak počet krokov totiž môžu byť tak vysoké, že pre bežné vstupy by polynomiálny algoritmus potreboval väčší počet krokov ---------- da sa dokazat ze: ku kazdej rastucej exponencialnej funkci f(x) = a^x s lubovolne malym zakladom "a" sprava blizkym k 1, existuje x0 take, ze pre vsetky x vacsie ako x0 je tato exponencialna funckia vacsia ako lubovolna polynomicka funkcia n-teho stupna v bode x0, t.j. f(x0) = a(n)*x0^n + a(n-1)*x0^(n-1) + a(n-2)*x0^(n-2) ... + a(3)*x0^3 + a(2)*x0^2 + a(1)*x0 + a(0) s lubovolnymi koeficiantami. Samozrejme ide o to, ako daleko je to x0.
|
neprihlásený 