Přeskočit na obsah

NP (třída složitosti)

Z Wikipedie, otevřené encyklopedie

NP (zkratka nedeterministicky polynomiální) je množina problémů, které lze řešit v polynomiálně omezeném čase na nedeterministickém Turingově stroji - na počítači, který umožňuje v každém kroku rozvětvit výpočet na n větví, v nichž se posléze řešení hledá současně. Ekvivalentně se hovoří o stroji, který na místě rozhodování uhodne správnou cestu výpočtu. Alternativně lze tyto problémy definovat tak, že je to množina problémů, u kterých lze pro dodaný výsledek v polynomiálním čase ověřit jeho správnost (ale obecně nikoliv nalézt řešení v polynomiálním čase).

Složitostní třída P je obsažena v NP, ale NP obsahuje velké množství důležitých problémů, zvaných NP-úplné, pro které není znám žádný polynomiální algoritmus. Pravděpodobně nejdůležitějším problémem současné informatiky (patří mezi Problémy milénia) je otázka, zda P = NP. Mnoho expertů věří, že P je vlastní podmnožinou NP.[1]

Příklady problémů v NP

[editovat | editovat zdroj]
  1. HEMASPAANDRA, Lane A. SIGACT News Complexity Theory Column 100 [online]. Dept. of Computer Science University of Rochester, 2019-03-19 [cit. 2025-05-20]. Dostupné online.