NP-hard problem

Angol

NP-hard problem (tsz. NP-hard problems)

(informatika) Egy probléma NP-nehéz (NP-hard), ha legalább olyan nehéz, mint a legnehezebb NP-problémák, azaz bármely NP-beli döntési probléma polinomiális időben visszavezethető rá. Formálisan:

Redukció Egy ismert NP-teljes (vagy NP-nehéz) döntési probléma ${\textstyle L'}$ polinomiális időben redukálható egy másik ${\textstyle L}$ problémára, ha létezik polinomiális idejű függvény

$f:{\text{példányok}}(L')\;\to \;{\text{példányok}}(L)$

olyan módon, hogy

$x\in L'\;\Longleftrightarrow \;f(x)\in L.$

Ez azt jelenti, hogy ${\textstyle L}$ legalább olyan nehéz, mint ${\textstyle L'}$ .
Nem kell NP-ben lennie Ellentétben az NP-teljes problémákkal, egy NP-nehéz feladat nem feltétlenül tartozik az NP-be — lehet, hogy a döntés igazolása sem polinomiális idejű. Sok optimalizációs, számérték-kimenetű vagy akár tetszőleges számítási feladat NP-nehéz (például a halting-probléma redukálható rájuk).

Travelling Salesman Problem (TSP) optimalizációs verzió – „Mekkora a legrövidebb Hamilton-kör összhossza a súlyozott gráfban?” – Döntési verzió (költség ≤ K?) NP-teljes, az optimalizáció önmagában NP-nehéz.
Knapsack (zsák-) optimalizáció – Maximális értékű részhalmazt keresünk súlykorlát alatt. A döntési kérdés NP-teljes, az optimalizáció NP-nehéz.
Graph Coloring minimalizálás – „Adott gráfban mi a minimális színek száma, hogy szomszédok különböző színt kapjanak?” Ez a döntési változat ${\textstyle k}$ -színezés NP-teljes.
Job-shop ütemezés – Több gépen, több feladat ütemezése minimális összkésésre vagy befejezési időre – NP-nehéz optimalizációs feladat.

NP-teljes = NP-ben van, és NP-nehéz.
NP-nehéz = legalább olyan nehéz, mint egy NP-teljes; nem kell NP-ben lennie.

Például:

A TSP-döntési (költség ≤ K?) NP-teljes.
A TSP-optimalizációs (minimális költség) NP-nehéz, de nem NP-ben (nem „igen/nem” kérdés).

Exponenciális algoritmusok – Teljes keresés, Branch & Bound, vágóegyenletek (cutting planes).
Közelítő algoritmusok (approximation) – Greedy, PTAS/FPTAS, logaritmikus közelítés (például set cover ${\textstyle O(\ln n)}$ ).
Heurisztikák és metaheurisztikák – Genetikus algoritmus, szimulált hőkezelés, tabu-keresés.
Paraméterezett (FPT) algoritmusok – Fix paraméter (pl. célköltség, erőforrás-keret) kis értéke esetén polinomiális a teljes bemenetre.

Egy probléma NP-nehéz, ha minden NP-feladat redukálható rá, azaz nem valószínű, hogy polinomiális algoritmusa létezik.
Gyakran optimalizációs verziók vagy olyan döntési feladatok, ahol a jutalom/költség nem igazolható egyszerűen.
A gyakorlati megoldások exponenciális, közelítő, heurisztikus vagy paraméterezett algoritmusok használatával kezelik ezeket az intractable feladatokat.