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 .
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 .
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 .
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 :
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 .
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.
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:
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.
Algoritmusok összetettségi osztályai | |
---|---|
Fénynek tekinthető | |
Állítólag nehéz | |
Nehéznek tartott |
|