NP-úplnost: Porovnání verzí

Hlavní důvod, proč jsou NP-úplné úlohy tak zajímavé, je právě jejich velmi obtížná řešitelnost. Díky ní nacházejí uplatnění v moderní [[kryptografie|kryptografii]], kde musímeje být schopnitřeba rychle ověřovat správnost řešení, ale jeho nalezení musí trvat dlouho. Obtížnost výpočtu ovšem záleží i na konkrétních datech — pro speciální množinu vstupů může být úloha polynomiální, například řešíme-li obarvení třemi barvami pro jednoduché grafy (cesty).