Array ( [0] => 14661663 [id] => 14661663 [1] => cswiki [site] => cswiki [2] => NP-úplnost [uri] => NP-úplnost [3] => [img] => [4] => [day_avg] => [5] => [day_diff] => [6] => [day_last] => [7] => [day_prev_last] => [8] => [oai] => [9] => [is_good] => [10] => [object_type] => [11] => 0 [has_content] => 0 [12] => [oai_cs_optimisticky] => ) Array ( [0] => '''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 (třída složitosti)|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]]. [1] => [2] => 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ů. [3] => [4] => == Příklady NP-úplných úloh == [5] => Mezi typické NP-úplné úlohy patří např. [[problém obchodního cestujícího]], tj. hledání (nejkratší) [[Hamiltonovská kružnice|hamiltonovské kružnice]], [[problém splnitelnosti booleovské formule]], hledání nezávislé množiny, problém [[Klika (teorie grafů)|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. [6] => [7] => == Využití NP-úplných úloh == [8] => 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í [[kryptografie|kryptografii]], kde je třeba 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). [9] => [10] => == Řešení NP-úplných úloh == [11] => * [[Aproximační algoritmy]] [12] => * [[Genetické algoritmy]] [13] => * [[Heuristické algoritmy]] [14] => * [[Pravděpodobnostní algoritmus|Pravděpodobnostní algoritmy]] [15] => * [[Prohledávání stavového prostoru]] hrubou silou, pokud je problém dostatečně malý [16] => {{Autoritní data}} [17] => [18] => [[Kategorie:Třídy složitosti]] [19] => [[Kategorie:NP-úplné problémy]] [] => )
good wiki

NP-úplnost

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.

More about us

About

Expert Team

Vivamus eget neque lacus. Pellentesque egauris ex.

Award winning agency

Lorem ipsum, dolor sit amet consectetur elitorceat .

10 Year Exp.

Pellen tesque eget, mauris lorem iupsum neque lacus.

You might be interested in

,'nedeterministicky polynomiální problém','polynomiální redukce','Kategorie:Třídy složitosti','Pravděpodobnostní algoritmus','Genetické algoritmy','kryptografie','NP (třída složitosti)','deterministický algoritmus','Problém P versus NP','problémy tisíciletí','Clayův matematický ústav','24. květen'

Kryptografie