NP-těžké problémy: vysvětlení, příklady a rozdíl od NP-úplnosti

NP-těžké problémy: vysvětlení, příklady a rozdíl od NP-úplnosti — srozumitelně, ilustrováno TSP a problémem zastavení, pro studenty, vývojáře a nadšence.

NP-těžký (NP-hard) označuje problém (obvykle rozhodovací nebo optimalizační), který je alespoň tak obtížný jako nejtěžší problémy z třídy NP. Formálně se obvykle řekne, že rozhodovací problém A je NP-těžký, jestliže pro každý problém B v NP existuje polynomiálně spočitatelná redukce z B na A. To znamená, že každou instanci problému B lze převést na instanci A v polynomiálním čase tak, že odpověď na původní instanci je „ano“ právě tehdy, když odpověď na převedené instanci A je „ano“.

Formální poznámky

• Redukce: Nejčastěji se používají polynomiální many-to-one (Karpovy) redukce. Jiné typy redukcí (Turingovy, Levinovy apod.) se také používají a mohou měnit třídu problémů, které jsou považovány za „těžké“.
• Nejsou vyžadovány žádné vlastnosti ověřitelnosti: NP-těžký problém nemusí být v NP a nemusí existovat rychlé (polynomiální) ověření „důkazu“ správnosti řešení.
• NP-úplný (NP-complete) znamená současně NP-těžký a patřící do NP. Tedy jde o rozhodovací problémy v NP, vůči nimž jsou všechny ostatní NP problémy redukovatelné.

Příklady

Příklad NP-těžkého problému, který je zároveň v NP (tedy NP-úplný):

Rozhodovací verze problému putujícího obchodníka (TSP): obchodník chce navštívit 100 měst a vrátit se domů. Má omezený nájezd 10 000 km. Otázka: existuje okružní cesta, která navštíví všechna města a jejíž délka nepřesahuje 10 000 km? Pokud nám někdo dá konkrétní pořadí měst (cestu), můžeme snadno spočítat její délku a ověřit, že je ≤ 10 000 km — ověření je polynomiální. Lidé neznají obecný rychlý (polynomiální) algoritmus, který by takové instance řešil, a tento rozhodovací TSP je příkladem problému, který je NP-těžký a zároveň patří do NP, tedy je NP-úplný. (Viz také problém putujícího obchodníka.)

V textu původně uvedený příklad: „Obchodní cestující chce autem navštívit 100 měst…“ popisuje právě rozhodovací verzi TSP, jejíž ověření je jednoduché — stačí předložit trasu a spočítat její délku. Tím ilustrujeme, co znamená, že problém je „rychle ověřitelný“.

Příklad NP-těžkého problému, který není v NP (tedy není rychle ověřitelný):

Problém zastavení (nebo jeho varianta) — například otázka „Pokud někdo spustí program:

while(true){ continue; }

a nikdy se nezastaví, poběží navždy?“ — nebo obecněji: „Běží daný program nekonečně dlouho / nikdy nezastaví?“ — patří mezi nerozhodnutelné problémy. Nerozhodnutelnost znamená, že neexistuje algoritmus, který by pro všechny vstupy za konečný čas (vždy) rozhodl správně. Problémy tohoto typu obvykle nelze ani ověřit pomocí krátkého důkazu, který by potvrzoval „ano“ v polynomiálním čase, takže nejsou v NP. Přitom lze ukázat, že mnohé nerozhodnutelné problémy (včetně variant problémů zastavení) jsou alespoň tak těžké jako libovolný problém z NP — tedy jsou NP-těžké. To se dělá tak, že se pro libovolnou instanci nějakého NP problému zkonstruuje stroj, který bude zastavovat právě tehdy, když původní instance má řešení; taková konstruktivní redukce ukáže, že nerozhodnutelný problém je NP-těžký.

Rozdíl mezi NP-těžký a NP-úplný

• NP-těžký: alespoň tak těžký jako libovolný problém v NP (v smyslu polynomiální redukce). Nemusí být rozhodovací, nemusí být ani rozhodnutelný, a nemusí mít rychle ověřitelné důkazy.
• NP-úplný: specifický podtyp NP-těžkých problémů, které navíc leží v NP. Jinými slovy NP-úplný = NP ∩ NP-těžký. Typické NP-úplné problémy: SAT (Splnitelná formule), Hamiltoniánský cyklus, rozhodovací TSP, apod.

Důsledky a užitečné poznámky

• Pokud by existoval polynomiální (rychlý) algoritmus pro některý NP-úplný problém, pak by se dal díky redukcím rychle (v polynomiálním čase) řešit každý problém z NP — tedy P = NP. To je hlavní důvod, proč jsou NP-úplné problémy považovány za „těžké“.
• Podobně platí i pro obecné NP-těžké problémy: pokud by nějaký NP-těžký problém (podle stejné definice redukcí) byl rozhodnutelný v polynomiálním čase, znamenalo by to, že P = NP (protože všechny NP problémy by se díky redukcím daly vyřešit v polynomiálním čase). Nicméně mnoho NP-těžkých problémů je nerozhodnutelných, takže je zřejmé, že je nelze zařadit mezi polynomiální algoritmy.
• NP-těžkost se vztahuje k těžkosti vzhledem k redukcím; existují také pojmy jako NP-úplné problémy vzhledem ke konkrétním typům redukcí (Karpovy, Levinovy, apod.), což může vést k jemně odlišným třídám „těžkých“ problémů.
• Optimalizační verze úloh (např. „najdi nejkratší možnou cestu“ v TSP) jsou často označovány za NP-těžké i když jejich rozhodovací verze může být NP-úplná. To se dělá proto, že pokud umíme optimalizační problém umět řešit v polynomiálním čase, dokážeme rozhodovací verzi i další NP úlohy redukcí vyřešit — tedy optimalizační úloha je „alespoň tak těžká“.

Shrnutí

NP-těžký problém je takový, že každému problému z NP lze efektivně převést instanci na instanci tohoto problému (polynomiální redukce). NP-úplné problémy jsou ty, které jsou NP-těžké a zároveň patří do NP (tedy jsou rychle ověřitelné). Do třídy NP-těžkých mohou patřit i nerozhodnutelné, neověřitelné či optimalizační problémy; příklady zahrnují rozhodovací TSP (NP-úplný) i problémy související s haltingem (ilustrující nerozhodnutelné, a přesto velmi těžké, případy). Pro pochopení obtížnosti problémů jsou klíčové pojmy redukcí a vztahů mezi třídami P, NP a dalšími komplexitními třídami.

Pokud chcete, můžu doplnit konkrétní formální definice redukcí, přidat známe NP-úplné problémy (SAT, 3-SAT, Hamiltonian cycle, CLIQUE, apod.) nebo ukázku jednoduché polynomiální redukce (např. ze SAT na 3-SAT nebo z 3-SAT na Hamiltonian cycle).

Otázky a odpovědi

Otázka: Co je NP-těžký problém?

Otázka: Lze rychle ověřit funkční řešení všech NP-těžkých problémů?

Otázka: Jak se nazývá kategorie NP-těžkých problémů, které jsou zároveň NP problémy?

Otázka: Jsou všechny NP-těžké problémy NP-úplné?

Otázka: Jsou NP-těžké problémy snadno řešitelné?

Otázka: Má řešení NP-těžkých problémů nějaké výhody?

Otázka: Probíhá výzkum v oblasti řešení NP-těžkých problémů?

Hledání podle dopisu