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 .

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 .

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:

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

  1. 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