NP je třída jazyků, které mají polynomiální časové verifikátory
Třída NP, která znamená „nedeterministický polynomiální čas“, je základním konceptem teorie výpočetní složitosti, podoblasti teoretické informatiky. Abychom porozuměli NP, musíme nejprve pochopit pojem rozhodovacích problémů, což jsou otázky s odpovědí ano-ne. Jazyk v tomto kontextu označuje sadu řetězců v nějaké abecedě, kde každý řetězec kóduje instanci rozhodovacího problému.
O jazyku (L) se říká, že je v NP, pokud pro (L) existuje ověřovatel v polynomiálním čase. Verifikátor je deterministický algoritmus (V), který přijímá dva vstupy: instanci (x) a certifikát (y). Certifikát (y) je také známý jako „svědek“ nebo „důkaz“. Ověřovatel (V) zkontroluje, zda certifikát (y) potvrzuje, že (x) patří do jazyka (L). Formálně je jazyk (L) v NP, pokud existuje polynomický-časový algoritmus (V) a polynom (p(n)) tak, že pro každý řetězec (x v L) existuje řetězec (y) s ( |y| leq p(|x|)) a (V(x, y) = 1). Naopak pro každý řetězec (x notin L) neexistuje řetězec (y) takový, že (V(x, y) = 1).
Chcete-li objasnit tento koncept, zvažte dobře známý problém "Booleovské satisfiability" (SAT). Problém SAT se ptá, zda existuje přiřazení pravdivostních hodnot proměnným v daném booleovském vzorci tak, že se vzorec vyhodnotí jako pravdivý. Problém SAT je v NP, protože daný booleovský vzorec ( phi ) a přiřazení ( alpha ) pravdivostních hodnot jeho proměnným, lze v polynomiálním čase ověřit, zda ( alpha ) splňuje ( phi ). Zde je instance ( x ) booleovský vzorec ( phi ) a certifikát ( y ) je přiřazení ( alpha ). Ověřovatel ( V ) kontroluje, zda ( alpha ) činí ( phi ) pravdivým, což lze provést v polynomiálním čase s ohledem na velikost ( phi ).
Dalším názorným příkladem je problém „Hamiltonské stezky“. Tento problém se ptá, zda v daném grafu existuje cesta, která navštíví každý vrchol právě jednou. Problém hamiltonovské cesty je také v NP, protože daný graf ( G ) a posloupnost vrcholů ( P ) lze v polynomiálním čase ověřit, zda ( P ) je hamiltonovská cesta v ( G ). V tomto případě je instance ( x ) graf ( G ) a certifikát ( y ) je posloupnost vrcholů ( P ). Verifikátor ( V ) kontroluje, zda ( P ) tvoří hamiltonovskou cestu, což lze provést v polynomiálním čase s ohledem na velikost ( G ).
Koncept ověřitelnosti v polynomiálním čase je důležitý, protože poskytuje způsob, jak charakterizovat problémy, které jsou efektivně kontrolovatelné, i když nalezení řešení může být výpočetně neproveditelné. To vede ke slavné otázce zda ( P = NP ), která se ptá, zda každý problém, jehož řešení lze ověřit v polynomiálním čase, lze také vyřešit v polynomiálním čase. Třída ( P ) se skládá z rozhodovacích problémů, které lze vyřešit v polynomiálním čase deterministickým Turingovým strojem. Pokud ( P = NP ), znamenalo by to, že každý problém s polynomiálním ověřovatelem má také polynomiální řešitel. Tato otázka zůstává jedním z nejdůležitějších otevřených problémů v informatice.
Jednou z klíčových vlastností NP je to, že je uzavřen pod polynomiálními redukcemi. Polynomiálně-časová redukce z jazyka ( L_1 ) na jazyk ( L_2 ) je polynomiálně vyčíslitelná funkce ( f ) taková, že ( x v L_1 ) právě tehdy, když ( f(x) v L_2 ). Pokud existuje polynomiálně-časová redukce z ( L_1 ) na ( L_2 ) a ( L_2 ) je v NP, pak ( L_1 ) je také v NP. Tato vlastnost je nápomocná při studiu NP-úplnosti, která identifikuje „nejtěžší“ problémy v NP. Problém je NP-úplný, pokud je v NP a každý problém v NP na něj může být redukován v polynomiálním čase. Problém SAT byl prvním problémem, který se ukázal jako NP-úplnost, a slouží jako základ pro prokázání NP-úplnosti dalších problémů.
Pro další ilustraci konceptu ověřitelnosti v polynomiálním čase zvažte problém "Součet podmnožin". Tento problém se ptá, zda existuje podmnožina dané sady celých čísel, která tvoří součty zadané cílové hodnoty. Problém součtu podmnožin je v NP, protože při dané množině celých čísel ( S ), cílové hodnotě ( t ) a podmnožině ( S' ) ( S ) lze v polynomiálním čase ověřit, zda součet prvků v (S') se rovná (t). Zde je instance (x) pár ((S,t)) a certifikát (y) je podmnožina (S'). Ověřovatel ( V ) kontroluje, zda se součet prvků v ( S' ) rovná ( t ), což lze provést v polynomiálním čase s ohledem na velikost ( S ).
Význam ověřitelnosti v polynomiálním čase přesahuje teoretické úvahy. V praxi to znamená, že u problémů v NP, pokud je předloženo navržené řešení (certifikát), lze jej efektivně zkontrolovat. To má významné důsledky pro kryptografické protokoly, optimalizační problémy a různé oblasti, kde je důležité ověřit správnost řešení.
Abychom to shrnuli, třída NP zahrnuje rozhodovací problémy, pro které lze navrhované řešení ověřit v polynomiálním čase deterministickým algoritmem. Tento koncept je základem teorie výpočetní složitosti a má hluboké důsledky pro teoretické i praktické aspekty informatiky. Studium NP, ověřitelnosti v polynomiálním čase a souvisejících konceptů, jako je NP-úplnost, je nadále pulzující a kritickou oblastí výzkumu.
Další nedávné otázky a odpovědi týkající se Komplexita:
- Není třída PSPACE rovna třídě EXPSPACE?
- Je třída složitosti P podmnožinou třídy PSPACE?
- Můžeme dokázat, že Np a P třída jsou stejné tím, že najdeme efektivní polynomické řešení pro jakýkoli NP úplný problém na deterministické TM?
- Může se třída NP rovnat třídě EXPTIME?
- Jsou v PSPACE problémy, pro které není znám žádný NP algoritmus?
- Může být problém SAT úplným problémem NP?
- Může být problém ve třídě složitosti NP, pokud existuje nedeterministický Turingův stroj, který jej vyřeší v polynomiálním čase
- Jsou P a NP vlastně stejnou třídou složitosti?
- Je každý bezkontextový jazyk ve třídě složitosti P?
- Existuje rozpor mezi definicí NP jako třídy rozhodovacích problémů s polynomiálními verifikátory a skutečností, že problémy ve třídě P mají také polynomiální verifikátory?
Podívejte se na další otázky a odpovědi ve Složitosti