V teoretické informatice jsou N a NP třídy složitosti, které popisují, jak obtížné je vyřešit určité problémy.
Třída P (polynomiální čas)
Než se dostaneme k NP, je důležité zmínit třídu P. Tato třída obsahuje všechny rozhodovací problémy (ano/ne), které lze vyřešit na deterministickém Turingově stroji v polynomiálním čase. Jinými slovy, existuje algoritmus, který dokáže daný problém vyřešit v čase O(nk)O(n^k)O(nk), kde kkk je nějaká konstanta.
Třída NP (nondeterministický polynomiální čas)
Třída NP zahrnuje všechny rozhodovací problémy, jejichž řešení lze ověřit v polynomiálním čase. To znamená, že pokud dostaneme nějaké “navržené řešení”, můžeme v polynomiálním čase ověřit, zda je správné.
Alternativní definice (pomocí nedeterministického Turingova stroje):
- NP obsahuje problémy, které lze vyřešit v polynomiálním čase na nedeterministickém Turingově stroji. Tento model stroje si může “hádat” správné řešení a ověřit ho v polynomiálním čase.
Rozdíl mezi P a NP
-
Pokud je problém v P, znamená to, že existuje efektivní algoritmus, který ho dokáže vyřešit.
-
Pokud je problém v NP, znamená to, že ověření řešení je snadné, ale nevíme, zda ho lze vždy najít efektivně.
-
Otázka, zda P = NP, je jedním z největších otevřených problémů v informatice.
NP-těžké a NP-úplné problémy
-
NP-těžké (NP-hard) – Problémy alespoň tak složité jako nejtěžší problémy v NP, ale nemusí být v NP (např. některé optimalizační problémy).
-
NP-úplné (NP-complete, NPC) – Problémy, které jsou zároveň v NP a jsou NP-těžké. Pokud by se našel polynomiální algoritmus pro jeden NP-úplný problém, všechny problémy v NP by šly řešit v polynomiálním čase.
Příklady
-
P: Seřazení čísel, násobení matic, hledání nejkratší cesty v grafu (Dijkstrův algoritmus).
-
NP: Problém obchodního cestujícího (TSP), splnitelnost booleovských formulí (SAT), batohový problém.
Shrnutí:
-
P = problémy řešitelné v polynomiálním čase.
-
NP = problémy, jejichž řešení lze ověřit v polynomiálním čase.
-
NP-úplné = nejtěžší problémy v NP.
-
NP-těžké = ještě těžší problémy, než NP (ale nemusí být v NP).