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.