NP‑keménység – definíció, NP‑teljesség és példák (TSP, megállási probléma)

NP‑keménység és NP‑teljesség magyarázata, szemléletes példákkal (TSP, megállási probléma). Ismerd meg definíciókat, példákat és döntési problémák lényegét egyszerűen.

Az NP‑kemény probléma (angolul NP‑hard) olyan döntési (igen/nem) probléma, amely legalább olyan nehéz megoldani, mint a legnehezebb olyan probléma, amelynek megoldása gyorsan (polinomiális idő alatt) ellenőrizhető. Formálisan azt mondjuk, hogy egy probléma H NP‑kemény, ha minden L ∈ NP‑re létezik polinomidőben számítható leképezés (ún. Karp‑vagy many‑one redukció) f úgy, hogy x ∈ L pontosan akkor, ha f(x) ∈ H.

NP maga a döntési problémák osztálya, amelyekre igaz, hogy minden „igen” válaszhoz létezik rövid (polinomiális hosszúságú) bizonyíték (certificate), és ezt a bizonyítékot determinisztikus Turing‑gép polinomidőben ellenőrizni tudja. Egy probléma akkor NP‑teljes (NP‑complete), ha egyrészt NP‑ben van, másrészt NP‑kemény — tehát a legnehezebb problémák közé tartozik az NP osztályon belül. Ha egy NP‑teljes problémára polinomiális idejű megoldás létezne, akkor minden NP‑beli probléma polinomiális időben megoldható lenne (ezért van a P vs NP kérdés középpontjában az NP‑teljes problémák vizsgálata).

Redukció és ellenőrzés (verifier)

Redukció: a polinomiális many‑one redukció egy polinomidőben kiszámítható függvény f, amely egy L‑beli példányt T‑beli példánnyá képez úgy, hogy x ∈ L ⇔ f(x) ∈ T. Ez egyértelműen lehetővé teszi, hogy ha T‑t gyorsan (polinomidőben) meg tudjuk oldani, akkor L‑t is megoldjuk.

Ellenőrzés (verifier): egy gondolatmenet NP‑re: ha egy „igen” példányra van egy rövid bizonyíték, a verifikáló algoritmus ezt a bizonyítékot polinomiális idő alatt megvizsgálja és döntést hoz. Például ha adott egy Hamilton‑kör és határérték, kiszámolható a kör hossza és összehasonlítható a határértékkel — ez gyorsan ellenőrizhető.

Példa: Utazó ügynök probléma (TSP) — NP‑teljesség

Példa a döntési formára: Adott egy súlyozott gráf (vagy távolságmátrix) és egy B szám; a kérdés: létezik‑e Hamilton‑kör, amelynek összhossza ≤ B? Ez a döntési változat általánosan NP‑teljes.

Konkrétan: „Egy utazó ügynök 100 várost akar felkeresni autóval, az útját otthon kezdi és fejezi be. A benzinkészlete korlátozott, ezért összesen csak 10 000 kilométert tud megtenni. Szeretné tudni, hogy el tud‑e látogatni minden várost anélkül, hogy kifogyna a benzin?” — ez a probléma a TSP döntési változatának egy példája.

Miért könnyű ellenőrizni egy megoldást? Ha valaki bemutat egy konkrét kört (a városok sorrendjét), akkor egy algoritmussal gyorsan kiszámolhatjuk a teljes megtett távolságot, és összehasonlíthatjuk a 10 000 km‑rel. Tehát a bemutatott kör bizonyítékként szolgál, és a verifikáció polinomiális időben (lineárisan a városok számához) elvégezhető.

Miért nehéz megtalálni a megoldást? Bár a megoldás ellenőrizhető, az ismert általános algoritmusok számára nincs ismert polinomiális időben működő eljárás; a legegyszerűbb „bruteforce” módszer minden lehetséges kör permutációját végigpróbálja, ami 100 város esetén gyakorlatilag kivitelezhetetlen. A TSP általános döntési formája NP‑teljes, így „legalább olyan nehéz”, mint bármely más NP problémáé.

Példa: Megállási (halting) probléma — NP‑kemény, de nem NP

A megállási probléma (halting problem) azt kérdezi: adott egy program (Turing‑gép) és egy bemenet, a program megáll (vagy elfut véges idő után) ezen a bemeneten? Alan Turing bizonyította, hogy ez a probléma általánosságban nem dönthető (azaz nincs olyan algoritmus, amely minden esetben megmondja a választ). Ezért a megállási probléma nem tartozik az NP‑be (még ha bizonyos részhalmazai ellenőrizhetők is lehetnek).

Ugyanakkor a megállási probléma NP‑kemény lehet: mivel bármely NP‑beli problémát (például a SAT‑ot) polinomiális időben át lehet alakítani olyan gép leírásává, amely épp akkor áll meg, ha az eredeti NP‑példány „igen” (például ha az input egy kielégíthető formula, a gép keres egy kielégítő hozzárendelést és akkor megáll). Mivel létezik ilyen polinomidőben előállítható átalakítás, a megállási probléma minden NP‑beli problémára vonatkozóan legalább olyan nehéz, azaz NP‑kemény. Mivel azonban a megállási probléma eldönthetetlen, nem tartozik NP‑be.

Példakód, ami soha nem áll meg (illusztráció):

while(true){ continue; }

A fenti program soha nem lép ki a ciklusból, így a megadott program‑példányra a megállási kérdés „nem”. Általánosságban azonban nem létezik algoritmus, amely minden tetszőleges programról és bemenetről megmondja, hogy megáll‑e — ezért a megállási probléma eldönthetetlen.

Összefoglalás és következmények

• NP: a „igen” példányok bizonyítéka polinomiálisan ellenőrizhető.
• NP‑kemény: minden NP‑beli probléma polinomiálisan redukálható rá; lehet, hogy nincs is algoritmikus megoldása (eldönthetetlen) vagy nem tartozik NP‑be.
• NP‑teljes: NP‑ben van és NP‑kemény; ezek a legnehezebb problémák az NP osztályban. Ha bármelyik NP‑teljes probléma polinomiális időben megoldható lenne, akkor P = NP.

Gyakorlati következmények: NP‑teljes és NP‑kemény problémák esetén gyakoriak a közelítő algoritmusok, heurisisztikák, speciális esetekre (pl. metrikus TSP) vagy véletlenszerűsített módszerek alkalmazása, mivel az általános, hatékony (polinomiális idejű) pontos algoritus nem ismert. A kriptográfia, a kombinatorikus optimalizálás és sok mérnöki feladat szorosan kapcsolódik ezekhez a fogalmakhoz.

Kérdések és válaszok

K: Mi az az NP-nehez probléma?

Kérdés: Minden NP-kemény problémára gyorsan ellenőrizhető egy működő megoldás?

K: Mi a neve annak a kategóriának, amely az NP-kemény problémáknak, amelyek egyben NP-problémák is?

K: Minden NP-kemény probléma NP-teljes?

K: Könnyen megoldhatóak az NP-kemény problémák?

K: Vannak-e előnyei az NP-nehez problémák megoldásának?

K: Folytatódik kutatás az NP-nehez problémák megoldása terén?

Keresés betűvel