Čo je NP-ťažkosť? Definícia NP-ťažkých problémov a príklady
Čo je NP-ťažkosť? Jasná definícia NP-ťažkých a NP-úplných problémov, rozdiel riešenia vs. overenia, s príkladmi (TSP, halting) a praktickými vysvetleniami.
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).
Otázky a odpovede
Otázka: Čo je NP-ťažký problém?
Odpoveď: NP-ťažký problém je typ matematického problému používaný v informatike, ktorý predstavuje problém typu áno/nie, ktorého nájdenie riešenia je minimálne rovnako ťažké ako nájdenie riešenia najťažšieho problému, ktorého riešenie sa dá rýchlo overiť ako pravdivé.
Otázka: Dá sa rýchlo skontrolovať funkčné riešenie pre všetky NP-ťažké problémy?
Odpoveď: Nie, len niektoré NP-ťažké problémy, nazývané NP problémy, majú riešenia, ktoré sa dajú rýchlo skontrolovať.
Otázka: Ako sa nazýva kategória NP-ťažkých problémov, ktoré sú zároveň NP problémami?
Odpoveď: NP-ťažké problémy, ktoré sú zároveň NP problémami, patria do kategórie nazývanej NP-úplné.
Otázka: Sú všetky NP-ťažké problémy NP-úplné?
Odpoveď: Nie, nie všetky NP-ťažké problémy sú NP-úplné. Do tejto kategórie patria len tie, ktoré sú zároveň NP problémami.
Otázka: Sú NP-ťažké problémy ľahko riešiteľné?
Odpoveď: Nie, NP-ťažké problémy sa neriešia ľahko. V skutočnosti je nájdenie ich riešenia prinajmenšom rovnako ťažké ako nájdenie riešenia najťažšieho problému, ktorého riešenie sa dá rýchlo overiť ako pravdivé.
Otázka: Má riešenie NP-ťažkých problémov nejaké výhody?
Odpoveď: Áno, riešenie NP-ťažkých problémov môže priniesť výhody v rôznych oblastiach, napríklad v informatike, fyzike a spoločenských vedách, pretože môžu vyžadovať zložité výpočty a modelovanie.
Otázka: Prebieha výskum v oblasti riešenia NP-ťažkých problémov?
Odpoveď: Áno, výskum v oblasti riešenia NP-ťažkých problémov pokračuje, pretože tieto problémy sú stále dôležité v rôznych oblastiach a nájdenie účinných algoritmov a riešení môže mať významné dôsledky.
Prehľadať