Verze z 28. 4. 2007, 03:37 editovat YonaBot (diskuse \| příspěvky) 5 895 editací m robot změnil: nl:NP-volledig ← Přejít na předchozí porovnání		Verze z 22. 6. 2007, 13:22 editovat zrušit editaci ToOb (diskuse \| příspěvky) 415 editací m →‎Příklady NP-úplných úloh 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]], tj. hledání (nejkratší) hamiltonovské kružnice, 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í