P vs NP – mi az? Definíció, jelentőség és NP-teljesség

Például, ha van egy problémánk, és valaki azt mondja: "A válasz a feladatra az 1, 2, 3, 4, 5 számok halmaza", a számítógép képes lehet gyorsan kitalálni, hogy a válasz helyes vagy helytelen, de nagyon sok időbe telhet, amíg a számítógép magától kitalálja az "1, 2, 3, 4, 5"-öt. Egy másik példa a prímszámok megtalálása. Könnyű ellenőrizni, hogy egy szám prím-e, de nagyon nehéz egyáltalán megtalálni ezeket a számokat. Néhány ilyen érdekes, gyakorlatias kérdésnél hiányzik bármilyen lehetőségünk arra, hogy gyorsan megtaláljuk a választ, de ha kapunk egy választ, akkor gyorsan ellenőrizhetjük - azaz ellenőrizhetjük - a választ. Ily módon az NP-problémákat úgy is elképzelhetjük, mint a rejtvényeket: egy rejtvényre nehéz lehet rájönni a válaszra, de ha egyszer meghalljuk a választ, a válasz nyilvánvalónak tűnik. Ebben az összehasonlításban (analógiában) az alapkérdés a következő: a rejtvények valóban olyan nehezek, mint gondoljuk, vagy valamit kihagyunk?

Mivel az ilyen P versus NP kérdések gyakorlati szempontból nagyon fontosak, sok matematikus, tudós és programozó szeretné bebizonyítani azt az általános tételt, hogy minden gyorsan ellenőrizhető probléma gyorsan megoldható. Ez a kérdés elég fontos ahhoz, hogy a Clay Matematikai Intézet 1 000 000 dollárt adjon annak, aki sikeresen szolgáltat egy olyan bizonyítást vagy érvényes magyarázatot, amely megcáfolja.

Ha kicsit mélyebbre ásunk, láthatjuk, hogy minden P probléma NP probléma: könnyen ellenőrizhető, hogy egy megoldás helyes-e a probléma megoldásával és a két megoldás összehasonlításával. Az emberek azonban az ellenkezőjére is kíváncsiak: Vannak-e más NP problémák is, mint P problémák, vagy minden NP probléma csak P probléma? Ha az NP problémák valóban nem azonosak a P problémákkal (P ≠ NP), akkor ez azt jelentené, hogy nem létezhetnek általános, gyors megoldási módok ezekre az NP problémákra, bármennyire is keresünk. Ha azonban minden NP probléma P probléma (P = NP), akkor ez azt jelentené, hogy léteznek új, nagyon gyors problémamegoldó módszerek. Csak még nem találtuk meg őket.

Mivel a tudósok és matematikusok minden igyekezete ellenére sem találtak még általános, egyszerű módszereket az NP-problémák megoldására, sokan úgy vélik, hogy vannak olyan NP-problémák, amelyek nem P-problémák (vagyis hogy P ≠ NP igaz). A legtöbb matematikus is úgy véli, hogy ez igaz, de jelenleg még senki sem bizonyította be szigorú matematikai elemzéssel. Ha sikerülne bebizonyítani, hogy az NP és a P ugyanaz (P = NP igaz), az óriási hatással lenne a mindennapi élet számos területére. Ezért a P versus NP kérdés fontos és széles körben vizsgált téma.

Tegyük fel, hogy valaki két tornyot akar építeni, különböző tömegű sziklák egymásra rakásával. Az ember azt akarja elérni, hogy mindkét torony tömege pontosan azonos legyen. Ez azt jelenti, hogy a köveket két azonos tömegű halomba kell rakni. Ha valaki kitalálja a sziklák felosztását, amiről úgy gondolja, hogy működni fog, akkor könnyen ellenőrizheti, hogy igaza volt-e. (A válasz ellenőrzéséhez a köveket két kupacba lehet osztani, majd mérleggel megnézni, hogy azonos-e a tömegük.) Mivel ezt az informatikusok által "Partíciónak" nevezett problémát könnyű ellenőrizni - egyszerűbb, mint egyenesen megoldani, mint látni fogjuk -, nem P-probléma. ^[]

Mennyire nehéz megoldani, egyenesen? Ha csak 100 kővel kezdünk, akkor 2^{100-1}-1 = 633,825,300,114,114,114,700,748,351,602,687, azaz körülbelül 6,3 x 10^{29} lehetséges módja (kombinációja) van annak, hogy ezeket a köveket két kupacra osszuk. Ha minden nap egy egyedi sziklakombinációt tudnánk ellenőrizni, akkor ez 1,3 x 10^{22} vagy 1.300.000.000.000.000.000.000.000.000 évnyi erőfeszítést igényelne. Összehasonlításképpen, a fizikusok szerint a világegyetem körülbelül 1,4 x 10^{10} éves (450 000 000 000 000 000 000 000 vagy körülbelül 4,5 x 10^{17} másodperc, vagyis körülbelül egy trilliomod része annak az időnek, ami a mi kőhalmozásunkhoz szükséges. Ez azt jelenti, hogy ha az univerzum kezdete óta eltelt összes időt vesszük, akkor másodpercenként több mint kétbillió (2 000 000 000 000 000) különböző kőzetfelosztási módot kellene ellenőrizni, hogy az összes különböző módot ellenőrizni tudjuk.

Ha egy nagy teljesítményű számítógépet úgy programoznánk, hogy a kövek felosztásának összes ilyen módját teszteljük, akkor a jelenlegi rendszerekkel talán 1 , 000 , 000 {\displaystyle 1,000,000} kombinációt tudnánk ellenőrizni másodpercenként. Ez azt jelenti, hogy még mindig 2 000 000 {\displaystyle 2 000 000 000} nagyon erős számítógépre lenne szükség, amelyek az univerzum keletkezése óta működnének, hogy a kőzetek felosztásának összes módját teszteljék.

Lehetséges azonban olyan módszert találni, amellyel a köveket két egyenlő halomra lehet osztani anélkül, hogy az összes kombinációt ellenőriznénk. A "P egyenlő NP-vel?" kérdés egy rövidítés arra a kérdésre, hogy létezhet-e ilyen módszer.

Sok fontos NP-probléma van, amit az emberek nem tudják, hogyan lehet úgy megoldani, hogy az gyorsabb legyen, mint minden lehetséges válasz kipróbálása. Íme néhány példa:

• Egy utazó ügynök 100 várost akar felkeresni autóval, és az útját otthon kezdi és fejezi be. A benzinkészlete korlátozott, ezért összesen csak 10 000 kilométert tud megtenni. Szeretné tudni, hogy el tud-e látogatni minden várost anélkül, hogy kifogyna a benzin.
• Egy iskolában 100 különböző osztály van, és a tanárnak minden osztály záróvizsgájához ki kell választania egy órát. A csalás megelőzése érdekében az összes diáknak, aki részt vesz egy órán, ugyanabban az időpontban kell vizsgáznia az adott órán. Ha egy tanuló egynél több órán vesz részt, akkor az összes vizsgát más-más időpontban kell letenni. A tanár azt szeretné tudni, hogy az összes vizsgát ugyanarra a napra tudja-e időzíteni, hogy minden tanuló minden órájából tudjon vizsgázni.
• Egy gazda 100 különböző tömegű görögdinnyét akar a piacra vinni. A dinnyéket dobozokba kell csomagolnia. Minden egyes dobozba csak 20 kilogramm fér el anélkül, hogy eltörne. A gazdálkodónak tudnia kell, hogy 10 doboz elég lesz-e ahhoz, hogy mind a 100 görögdinnyét a piacra vigye. (Ez triviális, ha egynél több görögdinnye nem nyom 2 kg-nál többet, akkor bármelyik 10 ládába beletehető, ha tíznél több görögdinnye nem nyom 2 kg-nál többet, akkor mindegyikbe beletehető egy-egy láda, stb. a gyors megoldáshoz; a megfigyelés lesz a kulcsa minden gyors megoldásnak, mint például ez vagy a számhalmaz-probléma).
• Egy nagy művészeti galériában sok terem van, és minden falat sok drága festmény borít. A galéria tulajdonosa kamerákat akar vásárolni, hogy megfigyelhesse ezeket a festményeket, arra az esetre, ha egy tolvaj megpróbálná ellopni valamelyiket. Azt szeretné tudni, hogy 100 kamera elég lesz-e ahhoz, hogy minden festményt legalább egy kamera láthasson.
• A klikkprobléma: Az iskola igazgatójának van egy listája arról, hogy mely diákok barátok egymással. Szeretné megtalálni a diákok 10%-ának egy olyan csoportját, amelyik mindannyian barátok egymással.

A fenti példában azt látjuk, hogy 100 {\displaystyle 100} kővel 2 100 {\displaystyle 2^{100}} módja van a kőhalmaz felosztásának. N {\displaystyle n} kővel 2 n {\displaystyle 2^{n}} kombináció létezik. Az f ( n ) = 2 n {\displaystyle f(n)=2^{n}} függvény egy exponenciális függvény. Azért fontos az NP szempontjából, mert modellezi a probléma megoldásához szükséges számítások legrosszabb esetben szükséges számát, és így a legrosszabb esetben szükséges időigényt.

És eddig a nehéz problémák megoldásához 2 n {\displaystyle 2^{n}} nagyságrendű számításokra volt szükség. Bármelyik probléma esetében az emberek megtalálták a módját annak, hogy csökkentsék a szükséges számítások számát. Lehet, hogy valaki kitalálja, hogy a legrosszabb esetben a számítások számának csak 1%-át kell elvégezni, és ezzel sok számítást megtakarít, de ez még mindig 0,01 × ( 2 n ) {\displaystyle 0,01\times (2^{n})} számítást jelent. És minden további kőzet még mindig megduplázza a feladat megoldásához szükséges számítások számát. Vannak olyan meglátások, amelyek a modell variációit előállító módszerekkel még kevesebb számítást végezhetnek: pl. 2 n / n 3 {\displaystyle 2^{n}/n^{3}}} . De az exponenciális függvény még mindig dominál, ahogy n {\displaystyle n} nő.

Tekintsük a vizsgák ütemezésének problémáját (lásd fent). De tegyük fel, hogy 15000 diák van. Van egy számítógépes program, amely mind a 15000 diák órarendjét felveszi. Egy óra alatt lefut, és kiad egy olyan vizsgaidőtervet, hogy az összes diák egy hét alatt meg tudja csinálni a vizsgáit. Ez rengeteg szabálynak megfelel (nincs egymás utáni vizsga, 28 órán belül nem lehet 2-nél több vizsga, ...), hogy korlátozza a vizsgahét stresszét. A program a félévközi szünetben egy órán keresztül fut, és mindenki tudja a vizsgarendjét, így bőven van ideje felkészülni.

A következő évben azonban már 10 diákkal többen vannak. Ha ugyanaz a program ugyanazon a számítógépen fut, akkor az egy órából 2 10 {\displaystyle 2^{10}} óra lesz, mert minden további diák megduplázza a számításokat. Ez 6 {\displaystyle 6} hét! Ha még 20 diák lenne, akkor

2 20 {\displaystyle 2^{20}} óra = 1048576 {\displaystyle 1048576}óra ~ 43691 {\displaystyle 43691} nap ~ 113 {\displaystyle 113} év

Így 15000 {\displaystyle 15000} diák esetében ez egy órát vesz igénybe. 15020 {\displaystyle 15020} diák esetében ez 113 {\displaystyle 113} évet vesz igénybe.

Amint láthatod, az exponenciális függvények nagyon gyorsan nőnek. A legtöbb matematikus úgy véli, hogy a legnehezebb NP-problémák megoldása exponenciális időt igényel.

A matematikusok ki tudják mutatni, hogy vannak olyan NP-problémák, amelyek NP-teljesek. Egy NP-teljes problémát legalább olyan nehéz megoldani, mint bármely más NP-problémát. Ez azt jelenti, hogy ha valaki találna egy módszert bármely NP-teljes probléma gyors megoldására, akkor ugyanezt a módszert minden NP-probléma gyors megoldására használhatná. A fent felsorolt problémák mindegyike NP-teljes, tehát ha az eladó talált egy módszert az utazás gyors megtervezésére, akkor ezt elmondhatja a tanárnak, aki ugyanezt a módszert használhatja a vizsgák ütemezésére. A farmer ugyanezzel a módszerrel meghatározhatná, hány ládára van szüksége, és a nő ugyanezzel a módszerrel találhatná meg a tornyok építésének módját.

Mivel egy olyan módszer, amely gyorsan megoldja az egyik ilyen problémát, az összeset megoldhatja, sokan vannak, akik meg akarják találni. Mivel azonban nagyon sokféle NP-teljes probléma létezik, és eddig még senki sem talált olyan módszert, amellyel akár csak egyet is gyorsan meg lehetne oldani, a legtöbb szakértő úgy véli, hogy az NP-teljes problémák gyors megoldása nem lehetséges.

Alapvető tulajdonságok

A számítási komplexitáselméletben a komplexitásosztály NP-teljes (rövidítve NP-C vagy NPC) a problémák olyan osztálya, amely két tulajdonsággal rendelkezik:

• Az NP (nemdeterminisztikus polinomiális idejű) problémák halmazába tartozik: A probléma bármely adott megoldása gyorsan (polinomiális időben) ellenőrizhető.
• Ez is az NP-nehezebb problémák közé tartozik: Azok, amelyek legalább olyan nehezek, mint az NP legnehezebb problémái. Az NP-nehez problémáknak nem feltétlenül kell az NP elemeinek lenniük, sőt, még az is lehet, hogy nem is eldönthetőek.

Hivatalos áttekintés

Az NP-teljes az NP egy részhalmaza, az összes olyan döntési probléma halmaza, amelynek megoldása polinomiális idő alatt ellenőrizhető; az NP-t ekvivalens módon úgy is definiálhatjuk, mint a gépen polinomiális idő alatt megoldható döntési problémák halmazát. Egy NP-ben lévő p probléma akkor és csak akkor tartozik az NPC-be, ha minden más NP-ben lévő probléma polinomiális idő alatt átalakítható p-be. Az NP-teljes jelzőt melléknévként kellett használni: az NP-teljes osztályba tartozó problémákat NP+teljes problémának nevezték.

Az NP-teljes problémákat azért tanulmányozzák, mert úgy tűnik, hogy a probléma megoldásának gyors ellenőrzésének képessége (NP) összefügg a probléma gyors megoldásának képességével (P). Úgy találták, hogy minden NP-ben lévő probléma gyorsan megoldható - ezt nevezik P = NP: problémakészletnek. Az egyetlen NP-teljes probléma gyorsan megoldható, gyorsabban, mint minden NP-teljes probléma szintén gyorsan megoldható, mert az NP-teljes probléma definíciója szerint minden NP-teljes problémának gyorsan redukálhatónak kell lennie minden NP-teljes problémára (polinomiális idő alatt redukálható). [1]

Példák

A Boolean kielégíthetőségi probléma NP-teljesnek tekinthető. Richard Karp 1972-ben 21 olyan problémát fogalmazott meg, amelyekről ismert, hogy NP-teljes. Ezek a Karp-féle 21 NP-teljes probléma néven ismertek. Ezek közé olyan problémák tartoznak, mint az egész számok lineáris programozási technikáját az egész számokra alkalmazó integer programozási probléma, a knapsack-probléma vagy a vertexfedési probléma.