NP-teljesség: az elmélet

Sokszor fogom használni azt a szót, hogy egy probléma NP-nehéz vagy NP-teljes. Azoknak viszont, akik sem bonyelmet, sem számtudot nem tanultak még, lehet, hogy ez nem mond túl sokat; ezt a lyukat próbálom betömni. Először is, hogy intuíciónk legyen:

Egy probléma NP-teljes, ha megoldását ellenőrizni könnyű,

de előállítani nehéz.

Ilyen például a SAT probléma, ami a következő (problémákat input/output specifikációval adok meg) :

• input: egy konjunktív normálformájú formula (CNF),
• output: 1, ha kielégíthető a formula (be lehet állítani 0/1-re a változóit úgy, hogy a végeredmény 1 legyen), 0 egyébként (ha mindig 0-t kapunk).

Először is, kiszámítani, hogy egy CNF kielégíthető-e vagy sem, persze ki lehet: egy félelmetesen alulkulturált módszer pl. kipróbálni az összes lehetséges értékadást. Ha van n változónk a formulánkban, ez 2ⁿ lehetőség, ami

gombócból is sok.

Ha mondjuk van száz változónk (most lehet, hogy van, aki azt hiszi, hogy ez sok - nem az), az 2¹⁰⁰ próbálkozás, ami egy 30-jegyű szám. Százbites. Ha másodpercenként 10¹⁰ próbát végzünk (egy 10GHz-es gép minden órajelében egyet, extrém munkavégzés), akkor 4*10¹², azaz

négybillió év alatt

végzünk is. Ez most ad egy jó képet arról, hogy mit értünk "előállítani nehéz" alatt. Persze abból, hogy van egy buta algoritmusunk, még nem kell, hogy bármi következzen, lehet, hogy van jobb is. Néhányan már látták biztos a rezolúció nevű csodát, ami pont erre a problémára egy algoritmus, de

a rezolúció is exponenciális időigényű,

ráadásul még exponenciális tárat is eszik hozzá legrosszabb esetben, szóval annyira nem nagy megtakarítás.

A fentiből még talán magyarázatra szorul az "exponenciális" szó, ez nyilván valami cⁿ vagy hasonló alakú függvény, valamilyen c-re és n-re. (Valójában nem csak n-t, hanem tetszőleges polinomot megengedünk kitevőben, de ez most nem olyan lényeges.) A futás- és tárigényről szóló képletekben n mindig az input mérete lesz, pl a SAT esetében az egész formulának mint pl stringnek a hossza. Nyilván még ha karakterenként új változó is jön mindig, akkor is egy n hosszú formulában legfeljebb n változó szerepel, így jön ki a 2ⁿ-es futásidő (precízebben, O(2ⁿ)-es futásidő -- az O(f(n)) azt jelenti megközelítőleg, hogy legfeljebb f(n), legalábbis valamilyen n-től kezdve.)

A helyzet az, hogy a SAT problémára a mai napig nem tudott senki olyan algoritmust mondani, mely szubexponenciális idő alatt garantáltan megoldja: a legjobb algoritmus ha jól emlékszem, 1.3ⁿ időigényű, ami kb 300 változóra hozza ugyanazt az időlimitet, mint a 2ⁿ-es 100 változóra, szóval not that much of a gain.

De senki nem tudta bebizonyítani, hogy nincs polinom időigényű (n, n², n³, ilyesmi) algoritmus - ez a számítástudomány legismertebb és legnagyobb nyitott kérdése, a

P =?= NP

-ként is ismert, melyet meg lehet úgy is fogalmazni, hogy vajon

megoldható-e a SAT polinomidőben vagy sem?

Jó, mondjuk egy n¹⁰⁰ időigényű algoritmus némi jóindulattal is a "mérsékelten hasznos" kategóriában indul, ott is a vigaszágon, de a gyakorlati tapasztalat azt mutatja, hogy ha valami gyakorlati problémára van polinomidejű algoritmus, akkor arra előbb-utóbb lesz kellemesen alacsony kitevőjű polinomiális algoritmus is.

Még nem szóltam az "ellenőrizni könnyű" részről. Úgy képzeljük, hogy ha egy kérdésre egy válasz "igen", akkor arra van valamiféle bizonyíték is. Például ebben az esetben ha egy CNF a SAT-nak egy "igen" példánya, azaz kielégíthető, az azért van, mert van egy kielégítő kiértékelés, a változók egy értékadása, ami igazra értékeli a formulát.

Egy ilyen kielégítő értékadás egy "tanú" az inputra.

Egy eldöntési (ez annyit jelent, hogy a kérdésre a válasz igen vagy nem) probléma akkor van NP-ben, ha van hozzá olyan tanúsítvány-rendszer, ami a következőket tudja:

• Egy I input ha "igen" példány, akkor van azt igazoló tanú.
• Egy I input ha "nem" példány, akkor nincs ilyen tanú.
• A tanúk "rövidek": van olyan p polinom (n, n², stb), hogy az n hosszú inputhoz tartozó tanúk legfeljebb p(n) hosszúak.
• A tanúk "könnyen ellenőrizhetőek": ha adott egy I input és egy T tanúsítvány, akkor azt szintén polinomidőben le tudjuk ellenőrizni, hogy T tényleg tanú-e I-hez.

Az utolsó két feltételt így együtt egyébként hívják "polinomidőben verifikálhatóság"-nak is.

A SAT-ra visszatérve: itt az input CNF-ekhez a változók kielégítő kiértékelései a tanúsítványok. Nyilván kielégítő kiértékelése pontosan a kielégíthető formuláknak van (ezért az első két feltétel azonnal teljesül is), a változó-értékadás n-bites, azaz rövid (megint miért - mert nem lehet több változó, mint amilyen hosszú az egész formula), és ha van egy értékadás, azt lineáris időben ki is lehet értékelni (csak végig kell menni a formulán és minden egyes klózra megnézni, hogy van-e benne 1 értékű literál - ez tényleg megy lineáris időben, ha az elején a kiértékelést egy tömbbe rakjuk). Ezért mondhatjuk, hogy a SAT NP-ben van, avagy polinomidőben verifikálható.

Az NP betűszó egyébként a nemdeterminisztikus polinomidő-ből jön, megközelíthetnénk az NP osztályt úgy is, mint a nemdeterminisztikus polinomidejű algoritmussal eldönthető problémák osztályát, de most a nemdeterminizmusra nem térnék ki.

Néhány további NP-beli probléma és a hozzájuk kapcsolódó tanúsítvány-rendszer, ami miatt NP-beliek:

• Elérhetőség: input egy n-csúcsú gráf, el lehet-e jutni az első csúcsából az n. csúcsába? Egy tanúsítvány-rendszer: a G gráf 1-es csúcsából az n-es csúcsába vezető út. (Nyilván az út csak n hosszú lehet maximum, könnyű ellenőrizni, hogy tényleg út-e, hisz csak az éleket kell ellenőrizni, hogy tényleg élek-e, és pont akkor van út 1-ből n-be, ha el lehet jutni, hát ez az elérhetőség definíciója.)
• Összetett számok: input egy N szám (binárisan! akkor ez logN bites input), kérdés: összetett szám-e? Egy tanúsítvány: az N szám egy valódi osztója egy tanú (rövid, az oszthatóságot könnyű tesztelni, és pont az összetett számoknak van valódi osztójuk, attól összetettek).
• Hamilton-út: input egy G gráf, van-e minden csúcsán pontosan egyszer átmenő út. Tanú: maga a Hamilton-út.
• Aknakereső: input egy részlegesen kitöltött Aknakereső-tábla, kérdés: konzisztens-e, azaz le lehet-e rakni úgy az aknákat, hogy minden felfedett szám mellé pont annyi akna kerüljön, amennyit a szám mond. Tanú: egy jó lerakás.

...stb. Rengeteg optimalizálási probléma is megfogalmazható "van-e olyan megoldás, aminek a költsége legfeljebb X" formában, ily módon ezek is NP-be esnek, ezért az NP egy gyakorlatból nagyon motivált osztály. (Várhatóan lesz sok NP-s poszt még, ha valakit ez még nem győzött meg :) )

Az "NP-teljes" annyit jelent intuitíve, hogy ugyan NP-beli a probléma, de azok közül a(z egyik)

legnehezebb.

A fenti listában pl. a Hamilton-út, az Aknakereső és a SAT NP-teljesek.

Az elérhetőségre és a prímtesztelésre ezzel szemben van polinomidejű algoritmus.

Az NP-teljes problémák egyikére se talált még senki, és nem is tudta bebizonyítani, hogy ilyen nincs.

(Próbálkozások azért vannak. Jó nincs köztük.)

Ahhoz, hogy ezt a teljességfogalmat kicsit mélyebben megértsük, meg kell ismerjük a 

visszavezetés

fogalmát, amit arra használunk, hogy tudjuk mondani, hogy az Y probléma legalább olyan nehéz, mint az X probléma (azért nem "nehezebb"-et mondok, mert egyforma nehezek is lehetnek). Ez a következőképp szól:

az X-nek Y-ra való visszavezetése egy gyors inputkonverzió, mely tartja a választ. Azaz, egy olyan f függvény, mely X inputjait alakítja át Y inputjaira oly módon, hogy ha az eredeti I input az X-nek "igen" példánya, akkor az átalakított f(I) input az Y-nak lesz "igen" példánya, "nem" példányból pedig "nem" példány lesz. Ez a választartás. A "gyors" pedig annyit tesz, hogy polinomidejű (ez már talán nem lepett meg senkit: az ökölszabály az, hogy valami akkor elég gyors, ha polinomidejű).

Például, az Aknakereső visszavezethető a SAT-ra: minden (i,j) mezőhöz hozzárendelünk egy x(i,j) logikai változót, amit akkor szánunk 1-re állítani, ha azon van akna és 0-ra, ha nincs, ezután csak össze kell éselnünk a számok által mondott feltételeket (pl egy 5-ös érték (i,j)-n azt mondja, hogy a körülötte levő 8 mezőből pontosan 5-ön van akna, amit ki lehet fejezni logikai formulával, hogy 8 változó közül pontosan 5 igaz. Akkor van hozzájuk CNF is. Ezeket kell összeéselni.), és ha a kapott formula kielégíthető, akkor az pont azt jelenti, hogy le tudunk rakni aknákat a táblára. (Ha ez gyors volt, nem baj, most nem olyan lényeges, látunk még ilyet. A lényeg, hogy van olyan gyors módszer, ami Aknakereső inputból SAT inputot készít választartó módon, ezért az Aknakereső visszavezethető a SAT-ra.)

Azért jelenti ez azt intuitíve, hogy az Aknakereső legfeljebb olyan nehéz, mint a SAT, mert ha a SAT-ra van algoritmusunk, akkor innen kezdve van az Aknakeresőre is: az input aknász táblát először átkonvertáljuk logikai formulává a visszavezetéssel, aztán ráengedjük a SAT solvert és a válaszból a választartás miatt megtudjuk, hogy az eredeti aknász táblánk konzisztens volt-e vagy sem.

(Amúgy vegyük észre, hogy ezzel egy kicsi, tízszer tízes táblából is hirtelen születik egy százváltozós SAT...)

Hogy a SAT NP-teljes, az azt jelenti, hogy NP-ben van és

minden NP-beli probléma visszavezethető rá.

mind. Az összes. Az elérhetőség, a Hamilton-út, az Aknakereső, a prímtesztelés, a TSP, a lineáris optimalizálás, minden NP-beli probléma. Ha a SAT-ot meg tudnánk oldani polinomidőben, akkor minden NP-beli problémát (inputkonverzió+SAT solver futtatásával) meg tudnánk oldani polinomidőben.

És mivel ez még senkinek nem sikerült, ezért a legtöbben úgy véljük, hogy nincs is ilyen algoritmus, vagyis P<>NP.

Ha egy probléma nehéznek látszik, és meg tudjuk mutatni, hogy NP-teljes (az NP-nehéz egyébként annyit jelent, hogy minden NP-beli probléma visszavezethető rá, de nem feltétlenül van NP-ben. Az ilyen problémák még sokkal nehezebbek lehetnek, mint bármelyik a fentiek közül. Egy ilyen pl. a Lemmings. Meg a Sokoban. Meg a sakk, a hex, és általában a jobb kétszemélyes játékok. A reguláris kifejezések ekvivalenciája is. Vannak nagyon nehéz problémák..), tehát ha meg tudjuk mutatni, hogy NP-teljes, az jó érv arra, hogy ne akarjuk feltétlenül megoldani, hanem például

elégedjünk meg közelítő megoldásokkal,

vagy

elégedjünk meg olyan algoritmussal, mely csak bizonyos inputokra működik,

és itt lép be a képbe a mestint, a heurisztikák és az approximáció.

Legközelebb esettanulmányokkal folytatom, lássuk ezt "élesben".