NP teljes probléma

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””.

Formális definíció

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. ${0,1}$ ${ABC}$ $\Sigma$ $\Sigma ^{*}$ $L$ $\Sigma$ $\Sigma ^{*}$ $L\subset \Sigma ^{*}$

A felismerés feladata egy nyelv esetében annak meghatározása, hogy egy adott szó a nyelvhez tartozik-e . $L$ $L$

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: $L_{1}$ $L_{2}$ $\Sigma$ $L_{1}$ $L_{2}$ $f\colon \Sigma ^{*}\ to \Sigma ^{*}$

$x\in L_{1}$ akkor és csak akkor . A karp redukálhatóságát vagy jelöléssel jelöljük . $f(x)\in L_{2}$ $L_{1}{\leq }_{p}L_{2}$ $L_{1}\varpropto L_{2}$

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. $L_{2}$

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$ $B$ $A$ $B$ $B$ $A$

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.

Erős értelemben vett NP-teljes

Egy feladatot szoros értelemben NP-teljesnek nevezünk , ha olyan részfeladata van, amely:

nem probléma a numerikus paraméterekkel (vagyis az ebben a feladatban talált mennyiségek maximális értékét felülről egy polinom határolja a bemenet hosszában)
NP-teljes.

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 .

Hipotézis P ≠ NP

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.

Példák NP-teljes problémákra

Lásd még

A P és NP osztályok egyenlősége

Jegyzetek

↑ William I. Gasarch. A P=?NP szavazás. (neopr.) // SIGACT News. - 2002. - T. 33 , 2. sz . - S. 34-47 . - doi : 10.1145/1052796.1052804 .
↑ Erik D. Demaine, Susan Hohenberger, David Liben-Nowell. A Tetris még hozzávetőlegesen is kemény . nyomtatás.

Irodalom

Gary M., Johnson D. Számítástechnikai gépek és nehéz problémák Archiválva : 2019. november 4., a Wayback Machine -nél . M.: Mir, 1982.
Thomas H. Kormen és munkatársai 34. fejezet NP-teljesség // Algoritmusok: Konstrukció és elemzés = Introduction to Algorithms. - 2. kiadás - M . : "Williams" , 2006. - 1296 p. — ISBN 0-07-013151-1 .
John Hopcroft , Rajiv Motwani, Jeffrey Ullman. Bevezetés az automataelméletbe, a nyelvekbe és a számításba. - M . : "Williams" , 2002. - 528 p. - ISBN 0-201-44124-1 .

Linkek

NP teljesség
A játékok és rejtvények számítási összetettsége archiválva 2006. december 6. a Wayback Machine -nél
Az NP optimalizálási problémák összefoglalója. Szerkesztők - Pierluigi Crescenzi, Viggo Kann Archiválva : 2006. december 5. a Wayback Machine -nél

Algoritmusok összetettségi osztályai
Fénynek tekinthető	DLOGTIME AC 0 ACC 0 TC0 [ hu L SL RL NL NC SC CC P P-complete ZPP RP BPP BQP EQP APX
Állítólag nehéz	U.P. NP NP kész co-NP társNP-teljes AM M.A. QMA PH ⊕P PP #P #P- IP_ PSPACE PSPACE-teljes
Nehéznek tartott	LEJÁRATI IDŐ NEXPTIME KIFEJEZÉS 2-EXPTIME ELEMENTARY R PR RE töltse ki újra Co-RE Co-RE-complete ÖSSZES

NP-teljes problémák
A halmozás (csomagolás) maximalizálási problémája	Csomagolás konténerekbe kétdimenziós csomagolás lineáris csomagolás súly szerinti csomagolás érték szerinti csomagolás A hátizsák probléma
gráfelmélet halmazelmélet	Csúcsborítási probléma Kattintson a probléma Egy független halmaz (halmaz) problémája Állítsa be a fedési problémát Steiner probléma Az utazó eladó probléma Általános utazó eladó probléma
Algoritmikus problémák	Kielégíthetőségi probléma Boole-képleteknél (konjunktív normál formában)
Logikai játékok és rejtvények	Általános címkék (játék N 2 -1-ben) legrövidebb megoldási probléma Problémák, amelyek megoldásait a Tetrisben alkalmazzák Általános Sudoku probléma Latin négyzet kitöltési probléma Kakuro feladata
Nehézségi osztályok Operációkutatás Optimalizálás Kombinatorikus optimalizálás Alkalmazott matematika Algoritmusok elmélete Dinamikus programozás 21 NP-teljes Karp probléma