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 Definice NP a polynomiální ověřitelnosti:
- 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
- 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?
- Je ověřovač pro polynom třídy P?
- Jaký je rozdíl mezi třídami P a NP v teorii výpočetní složitosti a jak souvisí s koncepty rozhodování a ověřování členství v jazycích?
- Popište proces konstrukce polynomiálního časového ověřovače z polynomiálního času nedeterministického Turingova stroje.
- Jak lze polynomiální časový verifikátor převést na ekvivalentní nedeterministický Turingův stroj?
- Vysvětlete dvě ekvivalentní definice třídy NP a jejich vztah k polynomiálním verifikátorům času a nedeterministickým Turingovým strojům.
- Co je to polynomiální ověřitelnost a jak souvisí s třídou NP?