Pochopení složitosti NP: definice a příklady

NP znamená „Nedeterministický polynomický čas“. Je to třída složitosti, která se týká množství času potřebného k vyřešení problému. V NP může být doba běhu algoritmu polynomiální ve velikosti vstupu, ale může být také nedeterministická, což znamená, že doba běhu se může lišit v závislosti na konkrétním řešení zvoleném algoritmem.

Jinými slovy, NP je třída problémů, které lze řešit v polynomiálním čase na nedeterministickém stroji. Nedeterministický stroj je stroj, který může paralelně zkoušet všechna možná řešení problému a přijmout to první, které funguje. To umožňuje stroji vyřešit některé problémy mnohem rychleji než deterministický stroj, který může zkoušet pouze jedno řešení najednou.…Některé příklady problémů v NP zahrnují:

* Problém cestujícího prodejce (uvedený seznam měst a jejich párové vzdálenosti, najít nejkratší možnou trasu, která navštíví každé město přesně jednou)
* Problém batohu (s ohledem na sadu položek a jejich hmotnosti a hodnoty určete podmnožinu položek, které se mají zahrnout do batohu s omezenou kapacitou, která maximalizuje celkovou hodnotu)
* Booleovský problém splnitelnosti (za předpokladu sady booleovských proměnných a jejich omezení určete, zda existuje přiřazení hodnot k proměnným, které splňuje všechna omezení)…
Třída složitosti NP je důležitá, protože zahrnuje mnoho problémů, které je obtížné vyřešit v polynomu čas, ale lze je rychle ověřit deterministickým strojem. To znamená, že i když algoritmus nemusí být schopen najít řešení v polynomiálním čase, může být stále užitečný, pokud dokáže rychle ověřit navržené řešení.