Archiv článků: NP úplné problémy

Autorovi jsme položili několik otázek týkajících se toho, nakolik má řešení úlohy obchodního cestujícího pomocí lineárního programování vztah problému P vs. NP, v současnosti jednomu z hlavních otevřených matematických problémů. Clayův matematický ústav za jejich řešení nabízí milion dolarů. Nejprve tisková zpráva Matematicko-fyzikální fakulty UK Na Matfyz putuje jedno z …

Jako subset sum se označuje úloha, kdy je na jedné straně zadána množina přirozených čísel, na druhé straně (větší) přirozené číslo. Ptáme se, zda v množině existuje podmnožina, jejíž součet dává dané číslo. Úloha patří do kategorie NP úplných problémů, to znamená, že s velikostí zadání (součtu i prvků podmnožiny) …