NP-teljes probléma - az algoritmusok elméletében az NP osztályból "igen" vagy "nem" választ tartalmazó probléma , amelyre ebből az osztályból bármely más probléma redukálható polinomiális időben (vagyis olyan műveletek segítségével, amelyek száma nem halad meg néhány polinomot az eredeti adat méretétől függően). Így az NP-teljes problémák bizonyos értelemben az NP osztály „tipikus” problémáinak egy részhalmazát alkotják: ha némelyikre találunk „polinomiálisan gyors” megoldási algoritmust, akkor az NP osztályból bármely más probléma megoldható. ugyanolyan „gyorsan””.
Az ábécé bármilyen véges karakterkészlet (például { } vagy {}). Az összes lehetséges szó halmazát ( ez az ábécé karaktereiből állóutolsó karakterlánc ) egy ábécé felett jelöli. Az ábécé feletti nyelv a halmazbármely részhalmaza , azaz.
A felismerés feladata egy nyelv esetében annak meghatározása, hogy egy adott szó a nyelvhez tartozik-e .
Legyen és legyen két nyelv az ábécé fölött . Egy nyelvet (Karp szerint) redukálhatónak mondunk egy nyelvre , ha létezik egy , függvény , amely polinomiális időben kiszámítható, és a következő tulajdonságokkal rendelkezik:
Egy nyelvet NP-keménynek mondunk , ha az NP osztály bármely nyelve redukálható rá. Egy nyelvet akkor mondunk NP-teljesnek , ha NP-kemény, és maga is az NP osztályba tartozik.
Informálisan szólva, az a tény, hogy a probléma problémára redukálódik, azt jelenti, hogy a probléma „nem nehezebb”, mint a probléma (mert ha meg tudjuk oldani , akkor meg tudjuk oldani és ). Így az NP-nehéz problémák osztályába tartoznak az NP-teljes problémák és a náluk "nehezebb" problémák (vagyis azok a problémák, amelyekre az NP-teljes problémák redukálhatók). Az NP osztály tartalmazza az NP-teljes problémákat és a náluk "könnyebb" problémákat (vagyis azokat a problémákat, amelyek NP-teljes problémákra redukálódnak).
A definícióból következik, hogy ha találunk olyan algoritmust, amely valamilyen (bármilyen) NP-teljes feladatot polinomiális időben megold, akkor az összes NP-probléma a P osztályba kerül, azaz polinomiális időben megoldódik.
Egy feladatot szoros értelemben NP-teljesnek nevezünk , ha olyan részfeladata van, amely:
Az ilyen problémák osztályát NPCS -nek nevezik . Ha a P ≠ NP hipotézis igaz, akkor nincs pszeudopolinomiális algoritmus az NPCS problémára .
A P és NP osztályok egybeesésének kérdése több mint harminc éve az egyik központi nyitott probléma . A tudományos közösség hajlamos nemleges választ adni erre a kérdésre [1] – ebben az esetben nem lehet polinomiális időben megoldani az NP-teljes problémákat.
Algoritmusok összetettségi osztályai | |
---|---|
Fénynek tekinthető | |
Állítólag nehéz | |
Nehéznek tartott |
|
NP-teljes problémák | |
---|---|
A halmozás (csomagolás) maximalizálási problémája |
|
gráfelmélet halmazelmélet | |
Algoritmikus problémák | |
Logikai játékok és rejtvények | |