NP úplnost

Od: martass* 19.05.09 18:19 odpovědí: 2 změna: 19.05.09 21:49

Dobrý den,
mám problém pochopit rozdíl mezi NP tezkym algoritmem a NP úplným problémem.
na wikipedii a i jinde na internetu jsem nachazel texty podobne tomuto:
NP-úplné problémy jsou takové nedeterministicky polynomiální problémy, na které jsou polynomiálně redukovatelné všechny ostatní problémy z NP. To znamená, že třídu NP-úplných úloh tvoří v jistém smyslu ty nejtěžší úlohy z NP. Pokud by byl nalezen deterministický polynomiální algoritmus pro nějakou NP-úplnou úlohu, znamenalo by to, že všechny nedeterministicky polynomiální problémy jsou řešitelné v polynomiálním čase, tedy že třída NP se „zhroutí“ do třídy P (NP = P).
vubec to nechapu, pisou, ze NP uplne problemy jsou ty nejtezsi problemy a pritom NP problemy, ktere jsou asi lehci redukujeme na NP uplne, tedy jeste na tezsi? proc?
dekuji

Odpovědět na otázku

2 odpovědi na otázku

Řazeno dle hodnocení

axus®

19.05.09 20:40

Spatne a presne naopak. Neredukujeme je, ale mame tu moznost je redukovat, protoze vsechny polynomialni problemy (NP) jsou podmnozinou tech nejtezsich, uplnych NP.

To ale neznamena, ze je redukovat musime. To by byla hloupost a hlavne zbytecnost. (Bylo by to stejne, jako pocitat obsah ctverce pomoci integralu, kdyz muzeme pouzit jednoduchy, znamy vzorec. Lze to, pac scitani je zjednodusene integrovani, ale je to zbytecne.)

Naopak plati, ze pokud by byl nalezen deterministicky postup pro (nejtezsi) NP-uplnou ulohu, pak musi logicky platit, ze kdyz vsechny NP jsou podmnozinou NP-uplne, kterou sme ale vyresili deterministicky, tak i jednotlive (lehci) NP jdou resit deterministicky. Tedy se znich stavaji pouhe P.

doplněno 19.05.09 20:42:

Pardon. V prvnim radku ma byt nedeterministicke polynomialni problemy a ne pouze polynomialni problemy...

martass*

19.05.09 21:49

dekuji za odpoved, uz tomu rozumim vic

jeste bych se chtel zeptat na mozne priklady NP tezkych a NP uplnych problemu. Vetsinou u obou dvou nalezam uplne stejne priklady jako: problem obchodniho cestujiciho, barevnost grafu, hledani kliky...

pritom v seznamu otazek ke statnicim mam podotazku "příklady NP-úplných a NP-těžkých problémů". Tak nevim jak odlisit tezke a ty nejtezsi, kdyz oboje jsou nedeterministicke polynomialni problemy.

dekuji.

[přidat komentář]

Přidat svou odpověď

Přihlásit se k odběru odpovědí z této otázky:

Neneseme odpovědnost za správnost informací a za škodu vzniklou jejich využitím. Jednotlivé odpovědi vyjadřují názory jejich autorů a nemusí se shodovat s názorem provozovatele poradny Poradte.cz.

Používáním poradny vyjadřujete souhlas s personifikovanou reklamou, která pomáhá financovat tento server, děkujeme.