Az NP azon nyelvek osztálya, amelyek polinomiális időellenőrzőkkel rendelkeznek
Az NP osztály, amely a "nemdeterminisztikus polinomiális időt" jelenti, a számítási komplexitás-elmélet alapvető fogalma, az elméleti számítástechnika egy részterülete. Az NP megértéséhez először meg kell ragadni a döntési problémák fogalmát, amelyek olyan kérdések, amelyekre igen vagy nem a válasz. A nyelv ebben az összefüggésben valamilyen ábécé feletti karakterláncok halmazára utal, ahol minden karakterlánc egy döntési probléma egy példányát kódolja.
Egy (L) nyelvről azt mondjuk, hogy NP-ben van, ha létezik (L) polinomiális idejű hitelesítő. A hitelesítő egy determinisztikus algoritmus (V), amely két bemenetet vesz igénybe: egy példányt (x) és egy tanúsítványt (y). Az (y) tanúsítványt „tanúnak” vagy „bizonyítéknak” is nevezik. A hitelesítő (V) ellenőrzi, hogy az (y) tanúsítvány megerősíti-e, hogy (x) az (L) nyelvhez tartozik. Formálisan egy nyelv (L) akkor van NP-ben, ha létezik egy polinom-idő algoritmus (V) és egy polinom (p(n)), így minden karakterlánchoz (x-ben L-ben) létezik egy karakterlánc (y) és ( |y|. leq p(|x|)) és (V(x, y) = 1). Ezzel szemben minden karakterlánchoz (x nem L) nincs olyan (y) karakterlánc, amelyre (V(x, y) = 1).
Ennek a fogalomnak a tisztázásához vegyük figyelembe a „boole-féle kielégíthetőség” (SAT) jól ismert problémáját. A SAT-probléma azt kérdezi, hogy létezik-e igazságérték-hozzárendelés a változókhoz egy adott logikai képletben úgy, hogy a képlet kiértékelése igaz legyen. A SAT-probléma az NP-ben van, mivel egy Boole-képlet (phi) és a változóihoz való igazságértékek hozzárendelése (alfa) polinomiális időben ellenőrizhető, hogy (alpha) kielégíti-e a (phi-t). Itt a példány (x) a logikai képlet (phi), a tanúsítvány (y) pedig a hozzárendelés (alpha). Az ellenőrző (V) ellenőrzi, hogy (alpha) igaz-e (phi)-e, ami polinomiális időben is elvégezhető a (phi) méretéhez képest.
Egy másik szemléltető példa a "Hamilton-ösvény" probléma. Ez a probléma azt kérdezi, hogy van-e olyan útvonal egy adott gráfban, amely pontosan egyszer látogat meg minden csúcsot. A Hamilton-út probléma is benne van NP-ben, mert adott gráf (G) és csúcssorozat (P), polinomiális időben ellenőrizhető, hogy (P) Hamilton-út-e (G-ben). Ebben az esetben a példány ( x ) a gráf ( G ), a tanúsítvány ( y ) pedig a csúcsok sorozata ( P ). A (V) ellenőrző ellenőrzi, hogy (P) alkot-e Hamilton-pályát, ami polinomiális időben is elvégezhető a ( G ) méretére vonatkozóan.
A polinomiális idejű verifikálhatóság fogalma azért fontos, mert lehetővé teszi a problémák hatékonyan ellenőrizhető jellemzését, még akkor is, ha a megoldás megtalálása számításilag nem kivitelezhető. Ez elvezet a híres-e (P = NP) kérdéshez, amely azt kérdezi, hogy minden olyan probléma, amelynek megoldása polinomiális időben igazolható, megoldható-e polinomiális időben is. A ( P ) osztály olyan döntési problémákból áll, amelyek polinomiális időben megoldhatók egy determinisztikus Turing-géppel. Ha ( P = NP ), az azt jelentené, hogy minden polinom idejű hitelesítővel végzett feladatnak van polinom idejű megoldója is. Ez a kérdés továbbra is az egyik legfontosabb nyitott probléma a számítástechnikában.
Az NP egyik legfontosabb tulajdonsága, hogy polinomiális idejű redukciók hatására zárt. Egy nyelvből (L_1) egy nyelvre (L_2) végzett polinomidő-redukció egy polinomidőben kiszámítható függvény (f) úgy, hogy (x az L_1-ben) akkor és csak akkor (f(x) az L_2-ben). Ha létezik polinomiális idejű redukció (L_1)-ből (L_2)-be, és (L_2) NP-ben van, akkor (L_1) is NP-ben van. Ez a tulajdonság fontos szerepet játszik az NP-teljesség vizsgálatában, amely azonosítja az NP "legnehezebb" problémáit. Egy probléma NP-teljes, ha NP-ben van, és minden NP-beli probléma redukálható rá polinomiális időben. A SAT probléma volt az első NP-teljesnek bizonyult probléma, és ez szolgál alapul más problémák NP-teljességének bizonyításához.
A polinomiális idejű ellenőrizhetőség fogalmának további szemléltetéséhez vegyük figyelembe a "Részhalmazösszeg" problémát. Ez a probléma azt kérdezi, hogy létezik-e az egész számok adott halmazának olyan részhalmaza, amely összegez egy meghatározott célértéket. A részhalmaz összege probléma azért van NP-ben, mert adott egész számok halmaza ( S ), célértéke ( t ) és ( S ) részhalmaza ( S' ), polinomiális időben ellenőrizhető, hogy az elemeinek összege (S') egyenlő (t). Itt a példány (x) az (S, t) pár, a tanúsítvány (y) pedig a részhalmaz (S'). Az ellenőrző (V) ellenőrzi, hogy az (S') elemeinek összege egyenlő-e (t), ami polinomiális időben is elvégezhető az (S ) méretéhez képest.
A polinomiális idejű ellenőrizhetőség jelentősége túlmutat az elméleti megfontolásokon. Gyakorlatilag ez azt jelenti, hogy az NP-ben felmerülő problémákra, ha rendelkezésre áll a javasolt megoldás (tanúsítvány), az hatékonyan ellenőrizhető. Ennek jelentős következményei vannak a kriptográfiai protokollokra, az optimalizálási problémákra és számos olyan területre, ahol fontos a megoldás helyességének ellenőrzése.
Összefoglalva, az NP osztály olyan döntési problémákat foglal magában, amelyekre a javasolt megoldás polinomiális időben igazolható egy determinisztikus algoritmus segítségével. Ez a koncepció a számítási komplexitás elméletének alapja, és mélyreható vonatkozásai vannak a számítástechnika elméleti és gyakorlati vonatkozásainak egyaránt. Az NP, a polinomiális idejű ellenőrizhetőség és a kapcsolódó fogalmak, például az NP-teljesség vizsgálata továbbra is élénk és kritikus kutatási terület.
További friss kérdések és válaszok ezzel kapcsolatban Bonyolultság:
- A PSPACE osztály nem egyenlő az EXPSPACE osztállyal?
- A P komplexitási osztály a PSPACE osztály részhalmaza?
- Bebizonyíthatjuk-e, hogy az Np és a P osztály azonos, ha hatékony polinomiális megoldást találunk bármely NP teljes feladatra egy determinisztikus TM-en?
- Egyenlő lehet az NP osztály az EXPTIME osztállyal?
- Vannak olyan problémák a PSPACE-ban, amelyekre nincs ismert NP algoritmus?
- Lehet egy SAT probléma NP teljes probléma?
- Lehet-e egy probléma NP komplexitási osztályban, ha van egy nem determinisztikus turinggép, amely polinomiális időben megoldja
- P és NP valójában ugyanaz a komplexitási osztály?
- Minden környezetfüggetlen nyelv a P komplexitási osztályban?
- Van-e ellentmondás az NP-nek mint döntési problémák osztályának polinomiális idejű hitelesítőkkel történő meghatározása és az a tény között, hogy a P osztályban lévő problémáknak polinomiális idejű hitelesítői is vannak?
További kérdések és válaszok a Complexity oldalon