NP-úplnost: Porovnání verzí
Verze 11487671 uživatele 90.179.206.199 (diskuse) zrušena |
Bez shrnutí editace |
||
| Řádek 1: | Řádek 1: | ||
'''NP-úplné''' ('''NP-complete''', '''NPC''') problémy jsou takové [[nedeterministicky polynomiální problém]]y, na které jsou [[polynomiální redukce|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 polynomiální [[deterministický 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). Otázka, zda nějaký takový algoritmus existuje, zatím nebyla rozhodnuta, předpokládá se však, že NP ≠ P (je však zřejmé, že P ⊆ NP). Více o tomto problému najdete v článku [[Problém P versus NP]]. |
'''NP-úplné''' ('''NP-complete''', '''NPC''') problémy jsou takové [[nedeterministicky polynomiální problém]]y, na které jsou [[polynomiální redukce|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 polynomiální [[deterministický 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). Otázka, zda nějaký takový algoritmus existuje, zatím nebyla rozhodnuta, předpokládá se však, že NP ≠ P (je však zřejmé, že P ⊆ NP). Více o tomto problému najdete v článku [[Problém P versus NP]]. |
||
Vztah mezi P a NP je jedním ze sedmi [[problémy tisíciletí|problémů tisíciletí]], které vypsal [[Clayův matematický ústav]] [[24. květen|24. května]] [[2000]] |
Vztah mezi P a NP je jedním ze sedmi [[problémy tisíciletí|problémů tisíciletí]], které vypsal [[Clayův matematický ústav]] [[24. květen|24. května]] [[2000]]. Za rozhodnutí vztahu nabízí 1 000 000 dolarů. |
||
== Příklady NP-úplných úloh == |
== Příklady NP-úplných úloh == |
||
Verze z 19. 10. 2014, 04:06
NP-úplné (NP-complete, NPC) 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 polynomiální deterministický 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). Otázka, zda nějaký takový algoritmus existuje, zatím nebyla rozhodnuta, předpokládá se však, že NP ≠ P (je však zřejmé, že P ⊆ NP). Více o tomto problému najdete v článku Problém P versus NP.
Vztah mezi P a NP je jedním ze sedmi problémů tisíciletí, které vypsal Clayův matematický ústav 24. května 2000. Za rozhodnutí vztahu nabízí 1 000 000 dolarů.
Příklady NP-úplných úloh
Mezi typické NP-úplné úlohy patří např. problém obchodního cestujícího, tj. hledání (nejkratší) hamiltonovské kružnice, SAT (splnitelnost formule v KNF), hledání nezávislé množiny, problém kliky (hledání úplného podgrafu), hledání isomorfního podgrafu, 3barevnost grafu, vrcholové pokrytí, zavazadlový problém (tzv. problém batohu), problém dvou loupežníků atd.
Využití NP-úplných úloh
Hlavní důvod, proč jsou NP-úplné úlohy tak zajímavé, je právě jejich velmi obtížná řešitelnost. Díky ní nacházejí uplatnění v moderní kryptografii, kde musíme být schopni rychle ověřovat správnost řešení, ale jeho nalezení musí trvat dlouho. Obtížnost výpočtu ovšem záleží i na konkrétních datech, pro speciální množinu vstupů může být úloha polynomiální, například řešíme-li obarvení třemi barvami pro jednoduché grafy (cesty).