Verze z 23. 11. 2006, 11:10 editovat Porthos (diskuse \| příspěvky) 74 638 editací m robot přidal: zh:NP完全 ← Přejít na předchozí porovnání		Verze z 20. 1. 2007, 18:03 editovat zrušit editaci Blahma (diskuse \| příspěvky) Prověření uživatelé, Správci 17 267 editací m →‎Příklady NP-úplných úloh: odkaz na výklad zkratky Přejít na další porovnání →
Řádek 4: == Příklady NP-úplných úloh == Mezi typické NP-úplné úlohy patří např. [[problém obchodního cestujícího]], SAT (splnitelnost formule v [[konjunktivní normální forma\|KNF]]), hledání hamiltonovské kružnice, hledání nezávislé množiny, problém kliky (hledání úplného podgrafu), hledání isomorfního podgrafu, 3-barevnost grafu, vrcholové pokrytí, zavazadlový problém (tzv. [[problém batohu]]), problém dvou loupežníků atd. == Využití NP-úplných úloh ==

NP-úplnost: Porovnání verzí