NP-úplnost: Porovnání verzí
Smazaný obsah Přidaný obsah
m robot přidal: no:NP-komplett |
mBez shrnutí editace |
||
Řádek 1:
'''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. To znamená, že třídu NP-úplných úloh tvoří v jistém smyslu ty ''nejtěžší'' úlohy z NP. Pokud by byl nalezen
Vztah mezi P a NP je jedním ze sedmi [[problémy tisíciletí|problémů tisíciletí]], které vypsal Clay Mathematics Institute [[24. květen|24. května]] [[2000]], za rozhodnutí vztahu nabízí 1 000 000 dolarů.
|