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:15:48
Podľa alternatívnej definície je problém typu NP, ak je možné správnosť riešenia problému overiť v polynomiálnom čase, hoci výpočet nemusí byť možné uskutočniť v polynomiálnom čase ---------- casto totiz overenie riesenia problemu je neporovnatelne jednoduchsie ako najst riesenie samotne a jedna sa o tzv. efekt padacieho mosta, resp. takmer-jednosmerne operacie. Overit spravnost faktorizacie zlozenych cisel na sucin niekolkych prvocisel ich vynasobenim je ako padnut do hlbokej priekopy s kolmymi smyklavymi stenami, priekopy zaplnenej vodou, ktora oddeluje hrad. To sa stane velmi lahko. Samotna faktorizacia je vsak ako dostat sa z tejto priekopy s hlbokymi, kolmymi a klzkymi stenami potom, co nam na prsty padne padaci most a odsekne nam ich. Nie je to nemozne, avsak neporovnatelne tazsie ako do priekopy padnut.
|
neprihlásený 