NP-úplnost: Porovnání verzí

Odebráno 21 bajtů ,  před 2 lety
 
== 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|hamiltonovské kružnice]], SAT (splnitelnost formule v [[konjunktivníproblém normálnísplnitelnosti forma|KNFbooleovské 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.
 
== Využití NP-úplných úloh ==