#1 12. 02. 2009 23:44
P versus NP
Pratele informatici, mel bych pro vas namet na zamysleni. Jake dusledky by melo, kdyby se dokazalo, ze hypoteza P \neq NP je nezavisle tvrzeni? Tedy laicky receno, ze ji nelze dokazat ani vyvratit? Napriklad u takove hypotezy kontinua je podle me suma fuk, jestli plati nebo ne, stejne to nikdo nikdy nebude schopen empiricky overit. Ale P versus NP je zasadni prakticky problem. Kdybych dokazal, ze nejde rozhodnout, jake nasledky by to melo treba pro problm obchodniho cestujiciho? Pokud na nej existuje polynomialni algoritmus, tak P = NP, pokud neexistuje tak P \neq NP. Co ale tedy muzu rict o optimalnim reseni obchodniho cestujiciho, jestlize je P \neq NP nezavisle?
Nothing in the world that's worth having comes easy.
Always do what you are most afraid of.
Offline
#2 13. 02. 2009 09:29
Re: P versus NP
↑ Lishaak: Řekl bych, že pro důkaz pravdivosti implikací
(existuje polynomiální algoritmus pro obchodního cestujícího) => P = NP
a
(neexistuje polynomiální algoritmus pro obchodního cestujícího) => P != NP
je třeba využít toho, že buď P = NP nebo P != NP a neexistuje žádná jiná třetí možnost. Pokud by třetí možnost existovala, tak výše uvedené implikace jsou nepravdivé a pro obchodního cestujícího tedy může, ale nemusí existovat polynomiální algoritmus a nic není proti ničemu.
Offline