NP-ťažkosť označuje triedu problémov, ktoré sú "aspoň také ťažké" ako najťažšie problémy z triedy NP. Formálne: rozhodovací problém L je NP-ťažký, ak pre každé jazykové (rozhodovacie) L' v NP existuje polynomiálna many-one redukcia f taká, že x ∈ L' práve vtedy, keď f(x) ∈ L. V neformálnejšom zmysle to znamená, že keby sme vedeli rýchlo (v polynomiálnom čase) riešiť nejaký NP-ťažký problém, vedeli by sme rýchlo riešiť všetky problémy z NP pomocou redukcií.
Rozdiel medzi NP, NP-ťažké a NP-úplné
NP (nondeterministic polynomial time) je trieda rozhodovacích problémov, ktorých správnosť odpovede "áno" možno overiť v polynomiálnom čase, ak máme vhodný dôkaz (certifikát).
NP-ťažký je širšia kategória: zahŕňa všetky problémy, ku ktorým sa dajú všetky problémy z NP pretransformovať pomocou polynomiálnej redukcie. Takýto problém nemusí byť sám rozhodovacím problémom a nemusí byť ani v NP.
Ak je problém zároveň v NP aj NP-ťažký, hovoríme, že je NP-úplný. Tieto problémy sú považované za "najťažšie" v NP — ak sa nájde polynomiálny algoritmus pre niektorý z nich, potom by to znamenalo P = NP a všetky problémy v NP by sa dali riešiť v polynomiálnom čase.
Príklady
Príklad NP-úplného rozhodovacieho problému (NP-ťažký a súčasne v NP):
Obchodný cestujúci chce navštíviť 100 miest autom, pričom svoju cestu začína a končí doma. Má obmedzené zásoby benzínu, takže môže prejsť celkovo len 10 000 kilometrov. Chce vedieť, či dokáže navštíviť všetky mestá bez toho, aby mu došiel benzín (teda či existuje okružná trasa s dĺžkou ≤ 10 000 km).
Ľudia nevedia, ako tento problém vyriešiť rýchlejšie než skúšaním mnohých (až exponenciálne mnohých) možností v najhoršom prípade, ale ak nám niekto predloží konkrétnu trasu (certifikát), môžeme pomocou algoritmu v polynomiálnom čase skontrolovať, či táto trasa navštevuje všetky mestá a či jej dĺžka je ≤ 10 000 km. Táto rozhodovacia verzia problému (s otázkou existencie trasy kratšej ako daný limit) je známa ako problém putujúceho predavača (TSP) — a jej rozhodovacia verzia je NP-úplná.
Príklad NP-ťažkého problému, ktorý typicky nie je v NP:
Optimalizačné verzie NP-úplných problémov sú často NP-ťažké, ale nie sú rozhodovacími problémami (čiže nie sú v triede NP, pretože NP definuje len rozhodovacie problémy). Napríklad: nájsť skutočne najkratšiu trasu v TSP (vrátane samotného výstupu tej trasy alebo numerickej hodnoty jej dĺžky) je optimalizačný problém, ktorý je NP-ťažký — overenie, že neexistuje kratšia trasa, nie je zvyčajne možné vykonať v polynomiálnom čase s krátkym certifikátom.
Mimo toho existujú problémy, ktoré sú ešte ťažšie (napríklad nerozhodnuteľné problémy ako problém zastavenia). Tieto problémy nemožno v všeobecnosti ani overiť v polynomiálnom čase a často sa radia mimo rámca NP. Ich porovnanie s NP závisí od typu redukcií a formálneho kontextu; z praktického hľadiska ich nazývame „omnoho ťažšie“ alebo jednoducho nerozhodnuteľné.
Ilustračný príklad s nekonečným cyklom
Ilustračný (neriešiteľný alebo nerozhodnuteľný) príklad:
while(true){ continue; }Otázka „bude tento program fungovať navždy (nikdy sa nezastaví)?“ je typom problému, ktorý súvisí s problémom zastavenia. Pre všeobecné programy neexistuje algoritmus, ktorý by vždy v konečnom čase povedal správnu odpoveď pre všetky vstupy. Takéto problémy nie sú v NP a ani ich riešenie či overenie nemožno vykonať pomocou jednoduchného polynomiálneho certifikátu.
Prečo je to dôležité
- NP-ťažkosť dáva formálny spôsob, ako porovnávať ťažkosti problémov: ak A redukujeme na B, potom B je (aspoň) tak ťažké ako A.
- Určenie, že problém je NP-ťažký (alebo NP-úplný), znamená, že pravdepodobne nemá efektívny (polynomiálny) algoritmus. V praxi to vedie k hľadaniu heuristík, aproximácií alebo špeciálnych prípadov riešiteľných rýchlo.
- Rozlíšenie medzi rozhodovacími a optimalizačnými verziami je dôležité: optimalizačné verzie sú často NP-ťažké, hoci ich rozhodovacia formulácia môže byť NP-úplná.
Stručne: NP-ťažký problém je taký problém, ku ktorému sa dajú všetky problémy z NP pretransformovať v polynomiálnom čase. Niektoré z týchto problémov sú aj v NP (a nazývame ich NP-úplné), iné sú mimo NP (optimalizačné, nerozhodnuteľné alebo inak ťažšie úlohy).