NP-tvrdosť
NP-ťažký problém je problém typu áno/nie, ktorého nájdenie riešenia je aspoň tak ťažké ako nájdenie riešenia najťažšieho problému, ktorého riešenie sa dá rýchlo overiť ako pravdivé. Niektoré NP-tvrdé problémy sú také, ktorých funkčné riešenie sa dá rýchlo skontrolovať (NP problémy) a niektoré nie. NP-ťažké problémy, ktoré sú zároveň NP problémami, patria do kategórie nazývanej NP-úplné.
Príklad problému, ktorý je prinajmenšom rovnako ťažký na riešenie ako akýkoľvek iný problém, ktorého riešenie môžeme rýchlo skontrolovať a ktorý je zároveň rýchlo kontrolovateľný (je NP-ťažký aj 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.
Ľudia nevedia, ako tento problém vyriešiť rýchlejšie ako testovaním každej možnej odpovede, ale ak sa nájde riešenie, ktoré to predajcovi umožní, môžeme pomocou algoritmu skontrolovať, či je to pravda. Tento problém je známy aj ako problém putujúceho predavača.
Príklad problému, ktorý je aspoň rovnako ťažký na riešenie ako akýkoľvek iný problém, ktorého riešenia môžeme rýchlo overiť, ale ktorý sa nedá rýchlo overiť (je NP-ťažký, ale nie je NP):
ak niekto spustí program, ktorý jednoducho ide,
while(true){ continue; }a nikdy sa nezastaví, bude fungovať navždy?
Neexistuje žiadny známy spôsob, ako nájsť riešenie všetkých problémov tohto druhu, a ani to sa nedá skontrolovať.
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.
