NP osztály

Az algoritmuselméletben az NP osztály (az angol non-deterministic polynomial szóból ) olyan megoldhatósági feladatok halmaza , amelyek megoldása egy Turing-gépen ellenőrizhető olyan idő alatt, amely nem haladja meg a bemenet méretére eső polinom értékét. adatokkal, néhány további információval (ún. határozati tanúsítvány ) .

Ezzel egyenértékűen az NP osztály olyan feladatokat tartalmaz, amelyek polinomiális időben megoldhatók egy nem determinisztikus Turing-gépen .

Azok a feladatok, amelyek polinomiális idejű megoldási algoritmussal rendelkeznek, sokkal gyorsabban megoldhatók számítógéppel, mint a közvetlen felsorolással, amelynek ideje exponenciális . Ez határozza meg a P és NP osztályok egyenlősége problémájának gyakorlati jelentőségét .

Definíciók

Az NP összetettségi osztály nyelvek halmazára van definiálva , azaz véges ábécé feletti szavak halmazaira . Egy L nyelvről azt mondjuk, hogy az NP osztályba tartozik, ha létezik a P osztályból egy kéthelyes predikátum ( vagyis polinomiális időben kiszámítható) és egy olyan állandó , amely minden x szóra az " x L -hez tartozik " feltétel ekvivalens azzal a feltétellel, hogy "van y hossza kisebb, mint olyan, hogy igaz " (ahol | x | az x szó hossza ). Az y szót annak a tanúsítványnak nevezzük , hogy x az L nyelvhez tartozik . Így ha van egy szó, amely a nyelvhez tartozik, és egy másik, korlátozott hosszúságú tanúszó (amit nehéz lehet megtalálni), akkor gyorsan ellenőrizhetjük, hogy x valóban L -hez tartozik . $\Sigma$ $R(x,\,y)$ $c>0$ $|x|^{c}$ $R(x,\,y)$

Egy ekvivalens definíciót kaphatunk a nem determinisztikus Turing-gép fogalmával (vagyis olyan Turing-géppel , amelynek programjának különböző egyenesei lehetnek ugyanazzal a bal oldallal). Ha a gép „villával”, azaz kétértelműséggel találkozott a programban, akkor a továbbiakban különböző számítási lehetőségek lehetségesek. A predikátumot , amely egy adott nemdeterminisztikus Turing-gépet reprezentál, akkor egyenlőnek tekintjük eggyel, ha van legalább egy számítási lehetőség, amely 1-et ad vissza, és nullának, ha minden opció 0-t ad vissza. Ha az 1-et adó számítás hossza nem halad meg valamilyen polinomot x hosszúságú , akkor az állítmányt az NP osztályba tartozónak nevezzük. Ha egy nyelvnek van egy predikátuma az NP osztályból, amely felismeri, akkor azt mondjuk, hogy a nyelv az NP osztályhoz tartozik. Ez a definíció egyenértékű a fent megadottal: tanúként a számításnál a kívánt elágazások számát veheti át a számításnál. Mivel a nyelvhez tartozó x esetén a teljes számítási út hossza nem haladja meg az x hosszúságú polinomot , akkor a tanú hosszát is korlátozza egy x hosszúságú polinom . $R(x)$

Bármilyen probléma az x szónak az L nyelvben való tagságával kapcsolatban , amely az NP osztályban található, exponenciális időben megoldható az összes lehetséges -nél kisebb hosszúságú tanúsítvány felsorolásával . A kvantumszámítógépen való megoldáshoz használhatja a GSA -t . Ebben az esetben a rendezendő összes lehetséges tanúsítvány számát a geometriai progresszió tagjainak összegének képletével határozhatjuk meg , amelynek nevezője megegyezik az ábécé karaktereinek számával, az első tag pedig 1 : $|x|^{c}$ $|x|^{c}$ $|\Sigma |$ $\Sigma$

$N={\frac {1-|\Sigma |^{|x|^{c}}}{1-|\Sigma |}}$

Ezért Q-bitekre van szükség a kívánt tanúsítvány megkereséséhez a GSA módszerrel . A tanúsítványt legfeljebb . $\left\lceil \log _{2}{\frac {1-|\Sigma |^{|x|^{c}}}{1-|\Sigma |}}\right\rceil$ $O\left({\sqrt {\frac {1-|\Sigma |^{|x|^{c}}}{1-|\Sigma |}}}\jobb)$

Kapcsolat más osztályokkal

A nyelvek azon osztályát, amelyek kiegészítései az NP-hez tartoznak, co-NP osztálynak nevezik , bár ez az osztály nem bizonyítottan különbözik az NP osztálytól. Az NP és a co-NP osztályok metszéspontja tartalmazza a P osztályt . Különösen az NP osztály tartalmazza a P osztályt. Ennek a felvételnek a szigorúságáról azonban semmit sem tudunk.

A P és NP osztályok egyenlőségének problémája az egyik központi nyitott probléma az algoritmusok elméletében. Ha egyenlőek, akkor az NP osztály bármely problémája gyorsan (polinomiális időben) megoldható. A tudományos közösség azonban hajlik erre a kérdésre a negatív válasz felé. [egy]

Az NP osztály más, tágabb osztályokba is beletartozik, például a PH osztályba . Nyitott kérdések is felmerülnek a többi osztályba való felvételének szigorúságával kapcsolatban.

Példák az NP osztály problémáira

Számos probléma említhető, amelyekről jelenleg nem tudni, hogy P-hez tartoznak-e, de az ismert, hogy NP-hez tartoznak. Közöttük:

Logikai képlet kielégítési problémája : egy adott logikai képletből megtudni, hogy van-e benne olyan változóhalmaz, amely 1-re változtatja. A tanúsítvány egy ilyen halmaz.
Klikk- probléma : Adott egy gráf , nézze meg, hogy tartalmaz -e adott méretű klikkeket (teljes részgráfokat). Tanúsítvány – a klikket alkotó csúcsok száma.
Hamilton-ciklus jelenlétének meghatározása gráfban . A tanúsítvány egy Hamilton-ciklust alkotó csúcsok sorozata.
Az utazó eladó probléma nem optimalizált változata (van-e egy adott k értéknél nem hosszabb útvonal) az előző probléma kiterjesztett és reálisabb változata. A tanúsítvány egy ilyen út.
Egész megoldás létezése adott lineáris egyenlőtlenségrendszerre. A tanúsítvány a megoldás.
Adott számú osztó hiánya úgy, hogy . Tanúsítvány – egy számot prímtényezőkre bont az elsődleges tanúsítványaikkal együtt . $m$ $d$ $1<d\leq k$ $m$

Az NP osztály összes problémája között megkülönböztethetők a „legnehezebbek” - NP-teljes problémák . Ha ezek közül bármelyik megoldható polinomiális időben, akkor az NP osztály minden problémája megoldható polinomidőben is.

Lásd még

Jegyzetek

↑ William I. Gasarch. A P=?NP szavazás. (neopr.) // SIGACT News. - 2002. - T. 33 , 2. sz . - S. 34-47 . - doi : 10.1145/1052796.1052804 .

Irodalom

Thomas H. Kormen és munkatársai Algoritmusok: Konstrukció és elemzés = Introduction to Algorithms. - 2. kiadás - M . : "Williams" , 2006. - 1296 p. — ISBN 0-07-013151-1 .
John Hopcroft , Rajiv Motwani, Jeffrey Ullman. Bevezetés az automataelméletbe, a nyelvekbe és a számításba. - M . : "Williams" , 2002. - 528 p. - ISBN 0-201-44124-1 .
Keresési feladatok. P és NP osztályok. Intelligencia. NP-Complete Problems archiválva 2011. június 13-án a Wayback Machine -nél
"Bevezetés a strukturális komplexitás elméletébe" . Előadás tanfolyam.

Algoritmusok összetettségi osztályai
Fénynek tekinthető	DLOGTIME AC 0 ACC 0 TC0 [ hu L SL RL NL NC SC CC P P-complete ZPP RP BPP BQP EQP APX
Állítólag nehéz	U.P. NP NP kész co-NP társNP-teljes AM M.A. QMA PH ⊕P PP #P #P- IP_ PSPACE PSPACE-teljes
Nehéznek tartott	LEJÁRATI IDŐ NEXPTIME KIFEJEZÉS 2-EXPTIME ELEMENTARY R PR RE töltse ki újra Co-RE Co-RE-complete ÖSSZES