NP nehézség

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2017. július 12-én felülvizsgált verziótól ; az ellenőrzések 4 szerkesztést igényelnek .

A számítási komplexitáselméletben az NP-keménység (nem-determinisztikus idő-polinomiális keménység) olyan problémák osztályának meghatározó tulajdonsága, amelyek informálisan "legalább olyan kemények, mint az NP legnehezebb problémái ". Az NP-nehéz probléma egyszerű példája a részhalmazösszeg probléma .

Formális definíció: Egy megoldhatósági probléma NP-nehéz, ha NP- ben bármelyik probléma polinomiális időben redukálható -ra . Egy ekvivalens feltétel megköveteli, hogy NP-ben minden probléma megoldható legyen polinomiális időben egy orákulum segítségével [1] [2] esetén . Következésképpen egy polinomiális idejű algoritmus bármely NP-nehéz probléma megoldására polinomiális idejű algoritmusokat ad az NP összes problémájára.

Úgy gondolják, hogy nem léteznek polinomiális idejű algoritmusok az NP-kemény problémákra, de ez nem bizonyított (lásd a P≠NP problémát ) [3] . Sőt, a P osztály , amelyben minden probléma polinomiális időben van megoldva, az NP osztályban [4] található .

Néhány NP-nehéz optimalizálási probléma polinomiálisan közelíthető valamilyen állandó (konstans) közelítési tényezőhöz (különösen az APX -ben ), vagy akár bármilyen közelítési tényezőhöz ( PTAS -ban vagy FPTAS -ban ).

Osztálynevek NP-keménységben

Az NP-nehéz problémáknak nem kell az NP komplexitási osztály elemeinek lenniük. Mivel az NP osztály a számítási komplexitáselmélet kulcsosztálya , ez a következő osztályok alapja:

NP Számítási döntési problémák osztálya, amelyekre adott pozitív döntés polinomiális idejű megoldásként igazolható egy determinisztikus Turing-géppel (vagy megoldható egy nem determinisztikus Turing-géppel polinomiális időben). NP-kemény (NP-kemény) A problémák egy osztálya, amelyek nem kevésbé bonyolultak, mint az NP legnehezebb problémái. Az NP-nehéz problémáknak nem kell az NP elemeinek lenniük; valójában az ilyen problémák akár megoldhatatlanok is lehetnek. NP-teljes (NP-teljes) A megoldhatósági problémák egy osztálya, amely az NP legnehezebb problémáit tartalmazza. Minden NP-teljes problémának NP-ben kell lennie, és minden más NP-teljes problémára redukálnia kell. NP-intermedier (NP-intermedier) A P és NP közötti köztes megoldhatósági problémák osztálya teljes, feltételezve, hogy a P és az NP osztályok különböznek egymástól. (Ha P=NP, akkor nincsenek NP-köztesek, mivel minden NP-ből (és P-ből) származó probléma ebben az esetben NP-teljesekre redukálódik, amelyek viszont ebben az esetben NP-ben és ennek megfelelően P-ben rejlenek)

Példák

Részhalmazösszeg probléma : Van-e egy adott egész halmaznak egy nem üres részhalmaza, amelynek összege nulla? Ez egy megoldhatósági probléma, és NP-teljes.

Az utazó eladó probléma egy olyan optimalizálási probléma, amely a legkisebb költséggel járó ciklikus útvonal megtalálását jelenti a súlyozott gráf összes csomópontján keresztül. Ez egy NP-nehéz probléma [5] .

A leállítási probléma olyan probléma, amely NP-nehéz, de nem NP-teljes. A feladat: „Adott egy program és annak bemenete, leáll a program?” Könnyen bebizonyítható, hogy a leállítási probléma NP-nehéz, de nem NP-teljes – a Boole -féle kielégítési probléma leállítási problémává redukálható, ha egy Turing-gép leírásává alakítjuk, amely minden lehetséges bemenetet kipróbál, és mikor talál olyat, amelyik kielégíti a képletet, leáll, különben végtelen hurokba lép. Ezenkívül a leállítási probléma nem szerepel NP-ben, mivel az NP-ben lévő összes probléma véges számú művelettel megoldható, és a megállítási probléma eldönthetetlen .

Vannak NP-nehéz problémák, amelyek nem NP-teljesek és nem is eldönthetetlenek . Például a valódi kvantifikált logikai formulák nyelve eldönthető polinomtérben , de nem determinisztikus polinomidőben (ha NP ≠ PSPACE igaz ) [6] .

Alkalmazások

Az NP-nehéz problémák leggyakrabban az alábbi területeken fordulnak elő:

Jegyzetek

  1. ↑ Az elméleti számítástechnika kézikönyve. - Amszterdam: Elsevier, 1998. - 1. évf. A, Algoritmusok és összetettség. — ISBN 0262720140 .
  2. ↑ Knuth, Donald (1974). Utóirat az NP-nehéz problémákról. ACM SIGACT Hírek . 6 (2): 15-16. DOI : 10.1145/1008304.1008305 .
  3. ↑ Shtetl-optimalizált » Blogarchívum » A P≠NP tudományos esete . www.scottaaronson.com . Letöltve: 2016. szeptember 25.
  4. ↑ PHYS771 6. előadás: P, NP és barátok . www.scottaaronson.com . Letöltve: 2016. szeptember 25.
  5. ↑ Lawler, E.L .; Lenstra, JK ; Rinnooy Kan, AHG & Shmoys, D.B. (1985), The Travelling Salesman Problem: A Guided Tour of Combinatorial Optimization , John Wiley & Sons, ISBN 0-471-90413-9 , < https://archive.org/details/travelingsalesma00lawl >  .
  6. ↑ Pontosabban ez a nyelv PSPACE-teljes ; lásd Wegener, Ingo (2005), Complexity Theory: Exploring the Limits of Efficient Algorithms , Springer, p. 189, ISBN 9783540210450 , < https://books.google.com/books?id=1fo7_KoFUPsC&pg=PA189 >  .