NP-hardness
NP-těžký problém je problém typu ano/ne, jehož nalezení řešení je přinejmenším stejně obtížné jako nalezení řešení nejtěžšího problému, jehož řešení lze rychle ověřit jako pravdivé. Některé NP-těžké problémy jsou takové, u nichž lze rychle ověřit funkční řešení (NP problémy), a některé ne. NP-těžké problémy, které jsou zároveň NP problémy, spadají do kategorie nazývané NP-úplné.
Příklad problému, který je přinejmenším stejně obtížný jako jakýkoli jiný problém, jehož řešení můžeme rychle ověřit a který je zároveň rychle kontrolovatelný (je NP-těžký i NP):
Obchodní cestující chce autem navštívit 100 měst, přičemž cestu začíná a končí doma. Má omezenou zásobu benzínu, takže může ujet celkem pouze 10 000 km. Chce vědět, zda může navštívit všechna města, aniž by mu došel benzín.
Lidé nevědí, jak tento problém vyřešit rychleji než testováním všech možných odpovědí, ale pokud se najde řešení, které to prodejci umožní, můžeme pomocí algoritmu ověřit, že je to pravda. Tento problém je také známý jako problém putujícího obchodníka.
Příklad problému, který je přinejmenším stejně obtížný jako jakýkoli jiný problém, jehož řešení můžeme rychle ověřit, ale který nelze rychle ověřit (je NP-těžký, ale není NP):
pokud někdo spustí program, který jednoduše funguje,
while(true){ continue; }a nikdy se nezastaví, poběží navždy?
Není znám způsob, jak najít řešení všech problémů tohoto druhu, a ani to nelze ověřit.
Otázky a odpovědi
Otázka: Co je NP-těžký problém?
Odpověď: NP-těžký problém je typ matematického problému používaný v informatice, který je problémem typu ano/ne, jehož nalezení řešení je přinejmenším stejně obtížné jako nalezení řešení nejtěžšího problému, jehož řešení lze rychle ověřit jako pravdivé.
Otázka: Lze rychle ověřit funkční řešení všech NP-těžkých problémů?
Odpověď: Ne, pouze některé NP-těžké problémy, tzv. NP problémy, mají řešení, které lze rychle zkontrolovat.
Otázka: Jak se nazývá kategorie NP-těžkých problémů, které jsou zároveň NP problémy?
O: NP-těžké problémy, které jsou zároveň NP problémy, patří do kategorie zvané NP-úplné.
Otázka: Jsou všechny NP-těžké problémy NP-úplné?
Odpověď: Ne, ne všechny NP-těžké problémy jsou NP-úplné. Do této kategorie spadají pouze ty, které jsou zároveň NP problémy.
Otázka: Jsou NP-těžké problémy snadno řešitelné?
Odpověď: Ne, NP-těžké problémy nejsou snadné na řešení. Ve skutečnosti je nalezení jejich řešení přinejmenším stejně obtížné jako nalezení řešení nejtěžšího problému, jehož řešení lze rychle ověřit jako pravdivé.
Otázka: Má řešení NP-těžkých problémů nějaké výhody?
Odpověď: Ano, řešení NP-těžkých problémů může přinést výhody v různých oborech, jako je informatika, fyzika a společenské vědy, protože mohou vyžadovat složité výpočty a modelování.
Otázka: Probíhá výzkum v oblasti řešení NP-těžkých problémů?
Odpověď: Ano, výzkum v oblasti řešení NP-těžkých problémů pokračuje, protože tyto problémy jsou stále důležité v různých oblastech a nalezení efektivních algoritmů a řešení může mít významné důsledky.
