Matematické Fórum
Nevíte-li si rady s jakýmkoliv matematickým problémem, toto místo je pro vás jako dělané.
Nástěnka
❗22. 8. 2021 (L) Přecházíme zpět na doménu forum.matweb.cz!
❗04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
❗23.10.2013 (Jel.) Zkuste před zadáním dotazu použít některý z online-nástrojů, konzultovat použití můžete v sekci CAS.
Nejste přihlášen(a). Přihlásit
#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