NP-hardness

Angol

NP-hardness (tsz. NP-hardnesses)

(informatika, mesterséges intelligencia) NP-hardness (NP-nehézség) egy kulcsfontosságú fogalom az algoritmuselméletben és számítási bonyolultságelméletben, amely azokat a problémákat írja le, amelyek legalább olyan nehezek, mint az összes NP-probléma – de nem feltétlenül tartoznak magába az NP osztályba.

NP (nondeterministic polynomial time) az a problémakör, amelyben:
- Egy megoldás ellenőrizhető polinomiális időben.
- Például: ha valaki ad egy megoldást egy Sudoku-ra, gyorsan ellenőrizheted, hogy jó-e.

Egy probléma NP-hard, ha minden NP-probléma polinomiális időben rá redukálható.

Ez azt jelenti, hogy:

Tulajdonság	NP-nehéz (NP-hard)	NP-teljes (NP-complete)
Megoldás ellenőrizhető polinomiálisan?	❌ Nem feltétlen	✅ Igen
Összes NP-re redukálható?	✅ Igen	✅ Igen
Tipikus példák	Optimalizálási problémák	Döntési változatok
Része az NP osztálynak?	❌ Nem mindig	✅ Igen

Probléma	Típus
Travelling Salesman Problem (TSP)	Legrövidebb út → optimalizálási változat
Knapsack (teljes, 0–1)	Optimalizálás
Job-shop scheduling	Ütemezési probléma
Bin Packing	Tárolási optimalizálás
3D protein folding	Bioinformatikai probléma
Subset sum (optimalizálás változat)	Kombinatorikus

Ahhoz, hogy egy probléma NP-hard legyen, bizonyítani kell:

Egy ismert NP-teljes problémáról polinomiális időben rávezethető.

Ez gyakran úgy történik, hogy:

Ismerünk egy már bizonyítottan NP-complete problémát (pl. SAT, 3-SAT, CLIQUE),
és azt módosításokkal átalakítjuk a vizsgált problémára (redukcióval).

NP-nehéz típus	Leírás
Döntési probléma	Általában NP-complete
Optimalizálási probléma	Általában NP-hard, de nem NP-ben
Konstruktív probléma	Pl. konkrét megoldás megkeresése
Folytonos vagy diszkrét	TSP diszkrét, fehérjeszerkezet-felgöngyölítés folytonos

Tudományos szempontból: Segít osztályozni, hogy mi oldható meg gyorsan, és mi nem valószínű.
Gyakorlati szempontból:
- Ha egy probléma NP-hard, nem remélhetünk általános hatékony algoritmust rá.
- Ezért használunk:
  - Heurisztikákat
  - Metaheurisztikákat (pl. genetikus algoritmusok, szimulált hűtés)
  - Közelítő algoritmusokat
  - Speciális esetekre pontos algoritmusokat

Fogalom	Leírás
NP-hard	Olyan probléma, amelyre minden NP-probléma polinomiálisan redukálható
Kapcsolat NP-vel	Lehet, hogy nem ellenőrizhető polinomiális időben
Tipikus példák	Optimalizálási feladatok
Fontosság	Megmutatja, mely problémák nem valószínű, hogy gyorsan megoldhatók
Következmény	Alternatív megközelítések szükségesek (heurisztikák, approximációk)