Episode I

Alice és Bob

8. fejezet

Alice és Bob biztonsága

Az előző fejezetben tovább osztályoztuk az algoritmikusan eldönthető problémákat aszerint, hogy a döntés milyen hatékonysággal hozható meg. Azt mondtuk, hogy hatékonyság szempontjából az a vízválasztó, hogy egy problémára létezik-e polinomiális időkomplexitású algoritmus vagy nem. Mutattunk néhány problémát, amelyekre jelenleg nem ismeretes ebben az értelemben hatékony algoritmus. Megismerkedtünk a $P$ és $NP$ problémaosztályokkal. Előbbibe azokat a problémákat soroltuk, amelyek eldönthetőek polinomiális időkomplexitású determinisztikus Turing-géppel. Utóbbiba pedig azokat, amelyekkel ugyanez megtehető nemdeterminisztikus Turing-géppel.

A tanú-tételt ismertetve megmutattuk, hogy ez utóbbi ekvivalens azoknak a problémáknak az osztályával, amelyek esetén az "igen" válasznak létezik polinomiális időben, determinisztikus Turing-géppel ellenőrizhető bizonyítéka. Végül megemlítettük a számítástudomány legjelentősebb megválaszolatlan kérdését, miszerint vajon e két problémaosztály megegyezik-e, vagy az általunk nehéznek gondolt problémák valóban nehezek. Ennek megválaszolása ugyanis kulcsfontosságú a kriptográfia szempontjából. De még ha nem is tudjuk ezt a kérdést jelenleg megválaszolni, miért lehetünk majdnem biztosak abban, hogy $P \neq = NP$ ? Hogyan tudjuk az algoritmikus problémák nehézségét összehasonlítani egymással? Melyek azok a problémák, amelyek minden más $NP$ -beli problémánál nehezebbek ilyen értelemben? Ebben a fejezetben erről lesz szó...

Figyelem! Ennek a fejezetnek a megértéséhez erősen ajánlott elolvasni a 6. és a 7. fejezeteket is.

Most visszanyúlunk az előző fejezetben ismertetett két nehéznek gondolt döntési problémához. A 3-színezhetőség problémája így hangzott: adott egy gráf, amelyről el kell dönteni, hogy a csúcsai kiszínezhetők-e legfeljebb $3$ színnel úgy, hogy a szomszédos csúcsok különböző színűek legyenek. Azokat a gráfokat, amelyekre ez teljesül, 3-színezhető gráfoknak neveztük. A k-függetlenség problémája pedig így hangzott: adott egy gráf és egy $k$ egész szám, és azt kell eldönteni, hogy ki lehet-e választani a gráfból $k$ darab csúcsot úgy, hogy ezek között a csúcsok között ne legyen él. Ezt úgy is mondhatjuk, hogy található-e a gráfban $k$ darab független csúcs. Azokat a gráfokat, amelyekre ez teljesül, k-független gráfoknak neveztük.

Mivel mindkét fenti probléma igencsak fontos az informatikában, ezért eléggé fájó, hogy egyikre sem ismeretes polinomiális időkomplexitású – azaz hatékony – algoritmus. E két döntési probléma között azonban algoritmikus komplexitási kapcsolat mutatható ki. Nevezetesen: bizonyítható, hogy az egyik "legalább olyan nehéz", mint a másik. Ez azt jelenti, hogyha a "nehezebbre" található polinomiális algoritmus, akkor a "könnyebbre" is. Megfordítva, ha a "könnyebbre" nem található polinomiális algoritmus, akkor a "nehezebbre" sem. De mit jelent pontosan, hogy egy döntési probléma "legalább olyan nehéz", mint egy másik?

8.1Problémák nehézségének összehasonlítása

Ennek megértéséhez döntési problémák helyett ismét az őket reprezentáló formális nyelvekre koncentrálunk, és bevezetjük az úgynevezett Karp-redukció fogalmát. Képzeljük el, hogy van két rekurzív nyelvünk, nevezzük őket $L$ -nek és $K$ -nak. Ezen kívül tegyük fel, hogy $f$ egy olyan rekurzív függvény, amely az összes $L$ -beli jelsorozathoz $K$ -beli jelsorozatot, míg az összes $L$ -en kívüli jelsorozathoz $K$ -n kívüli jelsorozatot rendel. A 7.6. szakaszban a tanú-tétel bizonyításánál alkalmazott "akkor és csak akkor" típusú mondatszerkezettel ez így fogalmazható meg: egy tetszőleges $x$ jelsorozat akkor és csak akkor mondata az $L$ nyelvnek, ha az $f (x)$ jelsorozat mondata a $K$ nyelvnek.

**8.1. ábra:** Nyelvbetartozást megtartó függvény

**8.2. ábra:** Nyelvbetartozást megsértő függvény

Azaz vagy egyszerre mindkettő állítás teljesül, vagy egyik sem, de olyan nincs, hogy az egyik igen, a másik pedig nem. De miért is olyan jó dolog ilyen függvényt találni?

Képzeljük el azt a szituációt, hogy egy olyan algoritmust szeretnénk készíteni, amely eldönti az $L$ nyelvbe tartozást, de sehogyan sem jövünk rá a megoldásra. Van viszont algoritmusunk a $K$ nyelvbe tartozás eldöntésére. Ha sikerülne találnunk egy olyan rekurzív $f$ függvényt, amely teljesíti a fenti tulajdonságot, akkor tulajdonképpen meglenne az algoritmusunk $L$ eldöntésére is. Ha ugyanis egy $x$ jelsorozatra el kell dönteni, hogy $L$ -be tartozik-e, nincs más dolgunk, mint kiszámítani az $f (x)$ jelsorozatot, majd erre a jelsorozatra lefuttatni a már létező, $K$ -ba tartozást eldöntő algoritmust. Ennek "igen" vagy "nem" válasza egyben megválaszolja az $x$ jelsorozat $L$ -be tartozásának kérdését is az $f$ függvény fenti tulajdonsága miatt. Ráadásul minden $x$ jelsorozatra véges időn belül megkapjuk a választ, hiszen az $f$ függvény rekurzív, tehát létezik olyan őt kiszámító Turing-gép, amely soha nem keveredik végtelen ciklusba.

Ha a fentieken kívül az $f$ függvényre még az is teljesül, hogy polinomiális időkomplexitású Turing-géppel kiszámítható, akkor azt mondjuk, hogy az $f$ függvény az $L$ nyelv Karp-redukciója a $K$ nyelvre. Ennek a fogalomnak a segítségével lényegében összehasonlíthatóvá válnak a döntési problémák a nehézségük szempontjából. Egy ilyen Karp-redukció létezése ugyanis azt jelenti, hogy az $L$ nyelv felismerése nem lényegesen nehezebb, mint a $K$ nyelv felismerése, leszámítva egy polinomiális időkomplexitású kis extra munkát, amit az $f$ függvény kiszámítása jelent. Az $L$ nyelv Karp-redukcióját a $K$ nyelvre így jelöljük: $L ≺ K$ . Most példaként megadunk egy Karp-redukciót a 3-színezhetőség és a k-függetlenség eldöntésének problémája között.

8.2Példa Karp-redukcióra

Ehhez egy olyan polinomiális időkomplexitású algoritmust kell találnunk, amely egy tetszőleges $G$ gráfból (azaz a 3-színezhetőség problémájának egy példányából) előállít egy $H$ gráfot és egy $k$ egész számot (azaz a k-függetlenség problémájának egy példányát), méghozzá úgy, hogy a $H$ gráf akkor és csak akkor legyen k-független, ha a $G$ gráf 3-színezhető. Az "akkor és csak akkor" mondatszerkezetet ismét a 8.1. szakaszban már említett szigorú értelemben kell venni.

A $H$ gráf és a $k$ egész szám előállítása $G$ -ből (tehát maga a Karp-redukció) a következő: másoljuk le a $G$ gráfot három példányban, és kössük össze azokat a csúcsokat éllel, amelyek ugyanannak az eredeti $G$ -beli csúcsnak a másolatai. Az így kapott "nagy" gráf legyen a $H$ , valamint $k$ értéke legyen az eredeti $G$ gráf csúcsainak száma, azaz jelen esetben $k = 5$ .

A fenti $G$ gráf a 3-színezhetőség problémának egy konkrét példánya, a csúcsokhoz rendelt $0$ , $1$ és $2$ számok a $G$ gráf egy konkrét színezését jelölik. Ebből a fenti Karp-redukció szerint képeztük a lenti $H$ gráfot és a $k$ egész számot, mint a k-függetlenség problémájának egy példányát. A $H$ gráf vízszintes szintjei a $G$ gráf kiterített másolatai. Mindegyik $G$ -beli színhez tartozik egy szint a $H$ gráfban: a $0$ színhez a felső, az $1$ színhez a középső, a $2$ színhez pedig az alsó szint. A függőleges irányítású élek azokat a csúcsokat kötik össze, amelyek ugyanannak a $G$ -beli csúcsnak a másolatai.

Most kezdjünk el végigmenni a $G$ gráf csúcsain szép sorban, és mindegyikhez jelöljük meg az ő $G$ -beli színének megfelelő szinten lévő másolatát a $H$ gráfban. Az így megjelölt csúcsokat vastagított körökkel jelöltük. Például $G$ -ben az $a$ csúcs színe $0$ , ezért jelöljük meg $H$ -ban az $a_{0}$ csúcsot. Hasonlóan, a $b$ csúcs színe $1$ , ezért jelöljük meg a $b_{1}$ csúcsot. És így tovább. Mire az eljárás végére érünk, épp $k = 5$ darab csúcs lesz megjelölve, hiszen az eredeti $G$ gráfnak épp ennyi csúcsa volt.

Most megmutatjuk, hogy épp egy k-független csúcshalmazt sikerült kijelölnünk $H$ -ban, azaz a megjelölt csúcsok között nincs él. Az adott szinten belül azért nincs közöttük él, mivel ha lenne, akkor a $G$ -beli eredetijük között is lenne, és így nem kerülhettek volna azonos szintre $H$ -ban, mivel kaphatták volna ugyanazt a színt. Függőleges irányú él pedig azért nincs, mert mindegyik oszlopból csak egy csúcsot jelöltünk meg $H$ -ban. Ez a gondolatmenet tetszőleges 3-színezhető $G$ gráf tetszőleges színezésére működik. Azt tehát már tudjuk, hogy ha a $G$ gráf 3-színezhető, akkor a $H$ gráf k-független.

Azt kell még megmutatnunk, hogy ha viszont a $G$ gráf nem 3-színezhető, akkor a $H$ gráf sem lehet k-független. Tegyük fel tehát, hogy a $G$ gráf nem 3-színezhető, azaz minimum $4$ szín kell a kiszínezéséhez. Ekkor a $H$ gráfban sem lehet $k = 5$ darab független csúcs, hiszen ha lenne, akkor végigmehetnénk rajtuk, és mindegyikük $G$ -beli eredetijét kiszínezhetnénk annak a $H$ -beli szintnek megfelelő színnel, amelyben helyet foglalnak. Így viszont $G$ -nek egy jó 3-színezését kapnánk, tehát $G$ mégiscsak 3-színezhető lenne, és ez ellentmondana a feltételezésünknek.

Természetesen egy Turing-gép vagy valódi számítógép számára ennél jóval pontosabb leírást kéne adnunk a fenti "átalakító" algoritmusra. A lényegen azonban ez nem változtatna. Most vizsgáljuk meg ennek az "átalakító" algoritmusnak a lépésszámát. Könnyen látható, hogy az a bemeneti $G$ gráf méretének polinomiális függvénye. Hiszen ha $G$ csúcsainak száma $n$ , éleinek száma pedig $e$ , akkor a belőle létrehozott $H$ gráf $3 n$ darab csúcsot és $3 n + 3 e$ darab élet fog tartalmazni. Másrészt $k$ értéke is könnyen számítható, hiszen csak meg kell számolni $G$ csúcsait. A fenti "átalakító" algoritmus tehát valóban egy a Karp-redukció a 3-színezhetőségről a k-függetlenség problémájára.

8.3Az NP problémaosztály krémje

A Karp-redukció fogalmának segítségével tehát egy adott $L$ nyelv felismerésének feladatát vissza lehet vezetni egy másik $K$ nyelv felismerésének feladatára. Egy $L ≺ K$ Karp-redukció létezése azt jelenti számunkra, hogy az $L$ nyelv felismerése nem lényegesen nehezebb a $K$ nyelv felismerésénél, leszámítva egy polinomiális időkomplexitású extra munkát. Ebből következik, hogy ha $K$ felismerésére van polinomiális idejű algoritmusunk, akkor $L$ -re is van. Fordítva: ha $L$ -re nincs polinomiális algoritmus, akkor $K$ -ra sincs. Az $NP$ nyelvosztály érdekes tulajdonsága, hogy léteznek benne ilyen értelemben "legnehezebb" nyelvek. Ezt világítjuk meg a következő definícióval.

Tegyük fel, hogy $K$ egy $NP$ -beli nyelv. Amennyiben tetszőleges, szintén $NP$ -beli $L$ nyelv esetén létezik $L ≺ K$ Karp-redukció, akkor azt mondjuk, hogy a $K$ nyelv NP-teljes. Az NP-teljes nyelvek felismerése tehát "legalább olyan nehéz", mint bármilyen más NP-beli nyelv felismerése. Amennyiben a kérdéses $K$ nyelvtől nem követeljük meg, hogy maga is $NP$ -ben legyen, úgy a $K$ nyelvet NP-nehéznek nevezzük. Az NP-teljes nyelvek tehát olyan speciális NP-nehéz nyelvek, amelyek maguk is $NP$ -ben vannak.

A fenti definíció egyszerű következménye, hogy amennyiben akár egyetlen NP-teljes nyelv eldöntésére is találnánk polinomiális algoritmust, abból következne, hogy $P = NP$ . Ha ugyanis akár egyetlen egy NP-teljes $K$ nyelv is a $P$ osztályban lenne, azaz felismerhető lenne polinomiális időkomplexitású algoritmussal, úgy minden $NP$ -beli $L$ nyelv szintén a $P$ osztályban lenne, hiszen az $L ≺ K$ Karp-redukció létezése miatt ebben az esetben az $L$ nyelvet is fel tudnánk ismerni polinomiális időkomplexitással. De megfordítva is igaz: amennyiben akár egyetlen NP-teljes nyelvről is kiderülne, hogy nem létezik őt felismerő polinomiális algoritmus, abból következne – azon kívül, hogy nyilván $P \neq = NP$ lenne – , hogy egyetlen NP-teljes nyelv felismerésére sem létezik polinomiális algoritmus. Ha ugyanis egy NP-teljes $L$ nyelvről bebizonyosodna, hogy a $P$ osztályon kívül van, akkor nem létezhet olyan NP-teljes $K$ nyelv, ami $P$ -ben van, máskülönben az $L ≺ K$ Karp-redukció létezése miatt az $L$ nyelvet is fel tudnánk ismerni polinomiális algoritmussal.

Vagyis minden NP-teljes nyelv vagy egyszerre polinomiális vagy egyszerre exponenciális időkomplexitású. Rendkívül sok algoritmikus probléma vezethető vissza NP-teljes nyelvek felismerésének feladatára. Éppen ezért eléggé bosszantó, hogy eddig – számtalan próbálkozás ellenére – egyetlen ilyen nyelvről sem tudtuk bizonyítani egyik eshetőséget sem.

Bonyolultságtérkép P nem egyenlő NP esetén — **8.4. ábra:** Bonyolultságtérkép $P \neq = NP$ esetén

Bonyolultságtérkép P egyenlő NP esetén — **8.5. ábra:** Bonyolultságtérkép $P = NP$ esetén

E két eshetőség közül a legtöbb matematikus az első elrendezést valószínűsíti. A gyakorlatban is előforduló algoritmikus feladatok között ugyanis nagyon gyakoriak az NP-teljes problémák. A szakirodalomban dokumentált NP-teljes feladatok száma jóval ezer felett van. Azonban ezek intenzív vizsgálata ellenére sem tapasztalható a polinomiális algoritmusok irányába történő legcsekélyebb előrehaladás. Így meglehetősen furcsa lenne, ha kiderülne, hogy ezek mindegyikére létezik hatékony algoritmus. Most mutatunk néhány, a gyakorlatban fontos algoritmikus optimalizálási feladatot, amelyek mind NP-teljes döntési problémákhoz vezetnek.

8.4NP-teljes és NP-nehéz problémák

Az alábbiakban néhány olyan, az informatikában is gyakran felmerülő optimalizálási feladatot ismertetünk, amelyek NP-teljes döntési problémákra vezethetők vissza.

Maximális méretű klikk keresése gráfokban

Egy gráfban klikknek nevezünk egy olyan csúcshalmazt, amelyen belül bármely két csúcs között van él. A feladat egy adott gráfban megtalálni a legnagyobb klikket.

**8.6. ábra:** Gráf 4 méretű maximális klikkel

Az ehhez a feladathoz tartozó döntési probléma így hangzik: adott $G$ gráf és $k$ egész szám esetén létezik-e $G$ -ben legalább $k$ darab csúcsot tartalmazó klikk? Ez a döntési probléma NP-teljes, amennyiben $k$ a bemenet része, azaz nem egy előre rögzített érték, amely az algoritmus létrehozásakor már ismert.

Megjegyezzük azonban, hogy amennyiben $k$ egy rögzített érték, úgy ebben az esetben könnyen konstruálhatunk polinomiális időkomplexitású algoritmust. Például ellenőrizhetjük az összes $k$ elemű csúcshalmazt, hogy van-e közöttük olyan, amelyik egy klikket alkot $G$ -ben. Habár ez egy nem túl hatékony algoritmus, azonban az ellenőrizendő csúcshalmazoknak a száma felülről becsülhető a $G$ gráf csúcsainak számának egy polinomjával.

Leghosszabb útvonal keresése gráfokban

Egy gráfban útvonalnak nevezzük csúcsok egy olyan sorozatát, amelyben bármely két egymást követő csúcs között van él, és a csúcsok nem ismétlődnek ebben a sorozatban. A feladat egy adott gráfban megtalálni a lehető leghosszabb (legtöbb élből álló) útvonalat két megadott csúcs között.

Az ehhez a feladathoz tartozó döntési probléma így hangzik: adott $G$ gráf, valamint $a, b$ csúcsok és $k$ egész szám esetén létezik-e $G$ -ben legalább $k$ hosszúságú útvonal $a$ -ból $b$ -be? Ez a döntési probléma szintén NP-teljes, amennyiben $k$ a bemenet része, azaz nem egy előre rögzített érték, amely az algoritmus létrehozásakor már ismert.

Ez utóbbi esetben viszont ismét könnyen konstruálhatunk polinomiális időkomplexitású algoritmust: egy $k$ hosszú útvonal ugyanis $k + 1$ csúcsból áll, így ellenőrizhetjük az összes $a$ -val kezdődő és $b$ -vel végződő $k + 1$ elemű csúcsokból álló sorozatot, hogy van-e közöttük olyan, amelyik egy útvonalat alkot $G$ -ben. Habár ez szintén egy nem túl hatékony algoritmus, de az ellenőrizendő sorozatoknak a száma ugyanúgy felülről becsülhető a $G$ gráf csúcsainak számának egy polinomjával, mint a klikkek esetében.

Érdekes ugyanakkor, hogy a legrövidebb útvonal megtalálására viszont léteznek polinomiális időkomplexitású algoritmusok. A legismertebb példák a használatukra a különböző navigációs alkalmazások útvonalkeresői. Az egyik leggyakrabban használt ilyen eljárás a Dijkstra-algoritmus.

Gráfok színezése

Gráfok színezéséről a 7.1. szakaszban már volt szó. A feladat egy adott gráf csúcsait a lehető legkevesebb szín felhasználásával kiszínezni oly módon, hogy bármely két szomszédos csúcs különböző színű legyen. Az ehhez a feladathoz tartozó döntési probléma így hangzik: adott $G$ gráf és $k$ egész szám esetén kiszínezhető-e $G$ legfeljebb $k$ darab szín felhasználásával?

A 7.3. szakaszban már említettük, hogy $k = 3$ esetén ennek eldöntésére jelenleg nem ismert polinomiális időkomplexitású algoritmus. Ráadásul nem is várható, hogy bárki felfedez ilyen algoritmust, ugyanis $k > 2$ esetén ez a döntési probléma is NP-teljes még abban az esetben is, ha $k$ nem a bemenet része, hanem egy előre rögzített érték.

Független csúcshalmaz keresése gráfokban

A független csúcsok problémájáról a 7.3. szakaszban volt szó. A feladat egy adott gráf csúcsai közül kiválasztani a lehető legtöbbet úgy, hogy ezek között ne legyen két egymással szomszédos csúcs. Az ehhez a feladathoz tartozó döntési probléma így hangzik: adott $G$ gráf és $k > 1$ egész szám esetén létezik-e $G$ -ben legalább $k$ darab csúcsot tartalmazó független csúcshalmaz?

A 7.3. szakaszban már említettük, hogy ennek eldöntésére sem ismert polinomiális időkomplexitású algoritmus. Valószínű, hogy nem is létezik, ugyanis ez a döntési probléma is NP-teljes, amennyiben $k$ a bemenet része, azaz nem egy előre rögzített érték, amely az algoritmus létrehozásakor már ismert.

Ez utóbbi esetben viszont – hasonlóan a maximális klikkméretre és leghosszabb útvonalakra vonatkozó döntési problémák esetén – könnyen konstruálhatunk polinomiális időkomplexitású algoritmust. Például ellenőrizhetjük az összes $k$ elemű csúcshalmazt, hogy van-e közöttük olyan, amelyik egy független csúcshalmazt alkot $G$ -ben. Az ellenőrizendő csúcshalmazoknak a száma ezúttal is felülről becsülhető a $G$ gráf csúcsainak számának egy polinomjával.

Az utazóügynök-probléma (egyszerűsített változat)

A feladat egy adott gráfban olyan útvonal keresése, amelyben a gráf összes csúcsa pontosan egyszer szerepel. Az ilyen útvonalakat Hamilton-útvonalaknak nevezzük. Az ehhez a feladathoz tartozó döntési probléma így hangzik: adott egy gráf, és el kell dönteni, hogy létezik-e benne Hamilton-útvonal. Ez a döntési probléma is NP-teljes.

Az utazóügynök-probléma a logisztikai problémákon túl nagy gyakorlati jelentőséggel bír például a nyomtatott áramkörök gyártása során alkalmazott fúrórobotok ideális mozgásának megtervezésében. De ezen kívül is rengeteg optimalizálási feladat vezethető vissza rá.

A hátizsák-probléma

Adott valahány darab tárgy, mindegyiknek meg van adva a súlya és az értéke, valamint adott egy valamilyen teherbírású hátizsák. A feladat a tárgyakból minél nagyobb összeértékű részhalmazt belepakolni a hátizsákba úgy, hogy ne lépjük át a súlyhatárt. Ezzel rokon probléma, amikor különböző méretű dobozokat kell bepakolni egy adott méretű szekrénybe úgy, hogy minél jobban kihasználjuk a rendelkezésre álló helyet. Ki ne bosszankodott volna például, amikor nyaralás előtt minél több mindent szeretett volna bepakolni a csomagtartóba? Most már tudjuk, hogy a bosszankodás oka az volt, hogy ez is egy NP-teljes döntési problémához vezet.

8.5Az NP-nehéz problémák kezelése

Jogosan merül fel a kérdés, hogy mitévők legyünk akkor, ha munkánk során olyan problémába ütközünk, amely bizonyítottan NP-nehéz. Ez ugyanis viszonylag gyakran előfordul, mégsem kell ezen problémák megoldásáról teljesen lemondanunk.

Az egyik lehetőség, hogy megvizsgáljuk, milyen méretű bemenetek várhatók a gyakorlati alkalmazás során, és olyan exponenciális időkomplexitású algoritmust keresünk, amely e bemenetméretek esetén is elfogadható idő alatt lefut. Erről a lehetőségről bővebben a 7.2. szakaszban volt szó.

Előfordulhat az is, hogy egy, a gyakorlatban felmerülő NP-nehéz problémáról kiderül, hogy valójában csak egy speciális esetét kell kezelnünk, amire már elképzelhető, hogy létezik polinomiális algoritmus.

Bevett módszer az is, hogy a problémára optimális, de lassú eljárás helyett az optimumnál rosszabb eredményt produkáló, de gyors algoritmust próbálunk keresni. Amennyiben bizonyítani tudjuk, hogy a gyors algoritmus eredményének az optimálistól való eltérése adott korlát alatt marad, úgy közelítő algoritmusról beszélünk.

Végül előfordulhat, hogy sikerül gyors algoritmust találnunk, amely közelíti ugyan az optimumot, de nem tudjuk bizonyítani azt, hogy a közelítés hibája adott korlát alatt marad, azonban a tapasztalat azt mutatja, hogy megfelelő eredményt ad a legtöbb esetben. Ezeket heurisztikus algoritmusoknak nevezzük.

8.6A Cook-Levin tétel

Előfordulhat, hogy egy algoritmikus problémát próbálunk megoldani, de sehogyan sem sikerül hatékony algoritmust találnunk. Ekkor jó lenne megnyugtatni magunkat, hogy ez nem azért nem sikerül, mert bénák vagyunk, hanem esetleg azért, mert maga a probléma NP-teljes. De hogyan tudnánk ezt igazolni? Ehhez a 8.3. szakaszban leírtak szerint az összes létező $NP$ -beli problémáról meg kéne mutatnunk, hogy Karp-redukcióval visszavezethető az általunk vizsgált problémára.

Szerencsére van egy ennél egyszerűbb módszer is, amely azon az észrevételen alapszik, miszerint az NP-teljesség a Karp-redukción keresztül "öröklődik". Ez a következőt jelenti: amennyiben egy $L$ nyelv NP-teljes, egy $K$ nyelv pedig $NP$ -ben van, továbbá létezik egy $L ≺ K$ Karp-redukció, akkor a $K$ nyelv is NP-teljes.

Ezt kihasználva tehát egy $K$ nyelv NP-teljességének bizonyításához nem szükséges, hogy redukáljuk az összes $NP$ -beli nyelvet $K$ -ra, elegendő ezt megtenni egyetlen NP-teljes nyelvvel. Vegyünk ugyanis egy tetszőleges $NP$ -beli $X$ nyelvet. Mivel a fenti öröklési tulajdonságban szereplő $L$ nyelv NP-teljes, ezért az $X$ nyelv felismerését polinomiális idejű extra munkával redukálni tudjuk az $L$ nyelv felismerésére. Ha az $L$ nyelv felismerését szintén polinomiális időben tovább tudjuk redukálni a $K$ nyelv felismerésére, akkor e két redukció egymás utáni alkalmazásával tulajdonképpen az $X$ nyelvet is redukálni tudjuk $K$ -ra polinomiálisan, azaz $K$ valóban NP-teljes.

Az öröklési tulajdonság alkalmazásához azonban szükségünk van legalább egy NP-teljes nyelvre, amiről tovább örökíthetnénk ezt a tulajdonságot más nyelvekre. Kiemelt jelentőségű volt emiatt Stephen Cook és Leonid Levin 1971-es eredménye, amely az első NP-teljes nyelvet mutatta meg. Ez az eredmény Cook-Levin tétel néven ismeretes. Ez a nyelv az úgynevezett kielégíthető logikai hálózatok nyelve. Egy logikai hálózat úgynevezett logikai kapukból és a közöttük lévő összeköttetésekből épül fel. Egy logikai kapunak vannak bemenetei, amelyek kétféle logikai értéket vehetnek fel: 1 vagy 0 (igaz vagy hamis). Ezenkívül van egy kimenete, amelyen a kapu szintén egy logikai értéket állít elő a típusának és a bemenetein lévő logikai értékeknek a függvényében.

Egy hálózat építéséhez 3 féle logikai kaput használhatunk:

ÉS-kapu: két bemenete van, a kimenetén pedig akkor és csak akkor állít elő 1-et, ha mindkét bemenetének értéke 1.
VAGY-kapu: szintén két bemenete van, a kimenetén pedig akkor és csak akkor állít elő 1-et, ha legalább az egyik bemenetének értéke 1.
NEM-kapu: egy bemenete van, a kimenetén pedig akkor és csak akkor állít elő 1-et, ha a bemenetének értéke 0.

E háromféle kapu működését az úgynevezett igazságtáblázatukkal adhatjuk meg, amely minden lehetséges bemeneti kombinációra megadja, hogy mi lesz a kimeneten.

**8.8. ábra:** ÉS-kapu jelölése és igazságtáblázata

**8.9. ábra:** VAGY-kapu jelölése és igazságtáblázata

**8.10. ábra:** NEM-kapu jelölése és igazságtáblázata

Egy logikai hálózat e kapuk segítségével a hálózat $n$ darab bemenetéből egy kimenetet állít elő. Egy kapu bármely bemenetére akármelyik másik kapu kimenetét, vagy közvetlenül a logikai hálózat valamely bemenetét köthetjük. Hasonlóan egy kapu kimenetét akármelyik másik kapu (vagy kapuk) bemenetére, vagy közvetlenül a logikai hálózat kimenetére köthetjük. Mindössze két megkötés van. Egyrészt minden kapu-bemenetre illetve a hálózat kimenetére is pontosan egy jel lehet kötve. Másrészt a hálózat tetszőleges bemenetétől a hálózat kimenetéhez vezető útvonalak mentén minden kapu legfeljebb egyszer fordulhat elő. Azaz nem lehetnek "hurkok" a hálózatban. Akkor beszélünk kielégíthető logikai hálózatról, ha létezik a bemeneteinek olyan kombinációja, amelyre a hálózat a kimenetén a logikai 1 értéket állítja elő.

**8.11. ábra:** Kielégíthető logikai hálózat (példa)

A logikai 1 értéket hordozó összeköttetéseket megvastagítottuk, így könnyen látható, hogy ez a bemeneti kombináció valóban a $D = 1$ kimenetet eredményezi. Ezek után a döntési feladatunk egy tetszőleges logikai hálózatról eldönteni, hogy kielégíthető-e a fenti értelemben. Formális nyelvekre átfogalmazva: nevezzük $SAT$ -nak az olyan jelsorozatokat tartalmazó nyelvet, amelyek egyrészt valamilyen logikai hálózat leírásai, másrészt az általuk leírt logikai hálózat a fenti értelemben kielégíthető. A feladatunk pedig egy olyan Turing-gép létrehozása, amely tetszőleges $x$ jelsorozatra eldönti, hogy a $SAT$ nyelvbe tartozik-e. A Cook-Levin tétel állítása a következő: a $SAT$ nyelv NP-teljes.

Annak bizonyítása viszonylag egyszerű, hogy a $SAT$ nyelv $NP$ -ben van, hiszen egy helyes kiértékelés – mint tanú – ellenőrzése hatékonyan megoldható, ahogy azt az olvasó a fenti példából érzékelhette. Az NP-teljességhez azonban azt is bizonyítani kell, hogy tetszőleges $NP$ -beli $L$ nyelvről létezik Karp-redukció a $SAT$ nyelvre. A Cook-Levin tétel bizonyítása lényegében egy olyan polinomiális időkomplexitású algoritmus leírása, amely egy tetszőleges $NP$ -beli $L$ nyelvhez és tetszőleges $x$ jelsorozathoz konstruál egy $y$ jelsorozatot (azaz az általa leírt logikai hálózatot) úgy, hogy az $x$ jelsorozat akkor és csak akkor tartozik $L$ -be, ha az $y$ jelsorozat $SAT$ -ba tartozik (azaz az általa leírt logikai hálózat kielégíthető).

A bizonyítás leírása hosszadalmas és erősen technikai jellegű, ezért ettől most eltekintünk. Arra azonban érdemes felhívni a figyelmet, hogy ezek szerint tetszőleges $NP$ -beli döntési probléma egy adott példányát le lehet írni egyetlen logikai kifejezéssel, vagy egy azt reprezentáló logikai hálózattal. Ez jól mutatja a logika kifejező erejét.

Ezen túlmenően a $SAT$ nyelv NP-teljességének önmagában is komoly jelentősége van. A valódi számítógépek integrált áramkörei ugyanis szintén a fentihez hasonló – persze annál lényegesen bonyolultabb – logikai hálózatokat valósítanak meg. Ezek optimalizálása épp az NP-teljesség miatt általában nem egyszerű. Optimalizálás alatt ebben az esetben ugyanannak a logikai hálózatnak a minél kevesebb logikai kapu használatával történő megvalósítását értjük.

A Cook-Levin tétel fontossága azonban elsősorban abban nyilvánul meg, hogy szinte az összes többi NP-teljességi bizonyítás – például a 8.4. szakaszban már említett 3-színezhetőség vagy k-függetlenség NP-teljessége is – közvetetten vagy közvetlenül a $SAT$ nyelv NP-teljességén alapszik.

8.7Egy meglepő fordulat

2015 novemberében Babai László, a Chicagoi Egyetem professzora bejelentette, hogy egy úgynevezett kvázipolinomiális időkomplexitású algoritmust talált a matematikusokat évtizedek óta foglalkoztató gráf-izomorfizmus problémára. A "kvázipolinomiális" fogalmát itt most nem részletezzük, azonban megpróbáljuk érzékeltetni a felfedezés jelentőségét.

Egy $G$ és $H$ gráfra akkor mondjuk, hogy izomorfak egymással, ha a csúcshalmazaik között létezik olyan kölcsönösen egyértelmű megfeleltetés, amely megőrzi az éleket illetve azok hiányát is. Ha tehát $G$ -ben veszünk két szomszédos csúcsot, akkor a nekik megfeleltetett csúcsok szintén szomszédosak lesznek $H$ -ban. Ugyanígy ha a két csúcs nem volt szomszédos $G$ -ben, akkor a nekik megfeleltetett csúcsok szintén nem szomszédosak $H$ -ban. A kölcsönösen egyértelműség pedig azt jelenti, hogy $G$ minden csúcsához pontosan egy csúcs van hozzárendelve $H$ -ban, és $H$ minden csúcsa pontosan egy $G$ -beli csúcshoz van hozzárendelve. Ilyenkor azt mondjuk, hogy a két gráf lényegében ugyanaz, maximum máshogyan lettek felrajzolva, vagy máshogyan neveztük el a csúcsaikat. Ilyenkor ezt a két csúcshalmaz közötti struktúratartó megfeleltetést – vagy ha úgy tetszik, függvényt – izomorfizmusnak nevezzük.

**8.13. ábra:** Nem izomorf gráfok (példa)

A gráf-izomorfizmus probléma ezek után így fogalmazható meg: adott két gráf, és el kell dönteni, hogy izomorfak-e vagy sem. Mindezidáig nagyon úgy tűnt, hogy ez egy rendkívül nehéz algoritmikus feladat nagy gráfok esetén. Ilyen esetekben korábban mindig az történt, hogy egy nehéznek tűnő problémáról vagy bebizonyosodott, hogy mégis hatékonyan kezelhető (azaz $P$ -beli), vagy pedig az, hogy NP-teljes.

Sokáig nyitott volt például az a kérdés, hogy egy egész számról eldönthető-e hatékonyan, hogy prímszám-e vagy összetett. 2002-ben azonban 3 indiai matematikus, Manindra Agrawal, Neeraj Kayal és Nitin Saxena felfedeztek egy polinomiális algoritmust ennek eldöntésére. Ennek neve a felfedezők neveinek kezdőbetűi után AKS-prímteszt, amelyről a 26.11. szakaszban lesz szó bővebben. Eddig is voltak természetesen prímtesztelő algoritmusok, hiszen – mint azt a 23. fejezetben látni fogjuk – fontos jelentőségük van a rejtjelezésben. De ezek mind csak bizonyos valószínűséggel adják meg a választ, azonban ritkán előfordulhat, hogy tévednek. A gyakorlatban továbbra is ezeket a potenciálisan tévedő eljárásokat használjuk prímtesztelésre, mivel jóval gyorsabbak, mint az AKS-algoritmus, és a tévedés valószínűsége az alkalmazás szempontjából elhanyagolható. Az AKS-algoritmusnak inkább elméleti jelentősége van, mivel megmutatta, hogy egy addig nehéznek tartott probléma nemhogy nem NP-teljes, de egyenesen $P$ -beli. Jóval gyakoribbak azonban azok az esetek, amikor egy nehéznek gondolt problémáról kiderül, hogy valóban NP-teljes.

Babai publikációját éppen ezért a matematikus társadalom, mint az évtized legnagyobb számítástudományi áttörését ünnepelte. Ebből az eredményből ugyanis nagyon úgy tűnik – még ha egyértelműen nem is következik belőle –, hogy a gráf-izomorfizmus problémája se nem NP-teljes, se nem $P$ -beli, azaz valahol a kettő között helyezkedhet el. Ha ez valóban így van, akkor ez lenne az első ilyen tulajdonságú probléma, amit felfedeztek, ráadásul a $P \neq = NP$ sejtésre is megadná végre a választ. Erre azonban egyelőre még várni kell.

8.8De hogy jön ide a kriptográfia?

Ahhoz, hogy Alice és Bob biztonságosan tudjanak egymással kommunikálni egy olyan csatornán keresztül, amelyet a gonosz Eve képes lehallgatni, szükségük van valamilyen rejtjelezési eljárásra. Ezen kívül szükségük van egy kulcsnak nevezett közös titokra is, amellyel az alkalmazott rejtjelezési eljárást paraméterezni fogják. A rejtjelezési eljárással szembeni legfontosabb követelmény, hogy a kulcs ismeretében "könnyű", annak hiányában viszont "nehéz" algoritmikus feladat legyen a rejtjelezett üzenetek dekódolása. A 6. és 7., valamint az ebben a fejezetben felvázolt bonyolultságelméleti fogalmak ismeretében az Olvasónak mostmár remélhetőleg világos, hogy pontosan mit értünk "könnyű" illetve "nehéz" algoritmikus feladat alatt.

Ezen túlmenően Alice-nak és Bob-nak azt a problémát is meg kell oldania, hogy hogyan tudnak megállapodni ebben a kulcsnak nevezett közös titokban anélkül, hogy személyesen találkozniuk kellene egymással. Ezt a kulcsmegosztás problémájának nevezzük. Ehhez a megállapodáshoz nyilván csak a nembiztonságos csatornát használhatják. De mégis hogyan lehetséges az, hogy a kulcsban való megállapodás érdekében küldött üzeneteket Eve ugyanúgy el tudja olvasni, mint Alice és Bob, mégsem tudja megfejteni magát a kulcsot – pontosabban fogalmazva az egy algoritmikusan roppant "nehéz" feladat a számára?

Erre a látszólagos paradoxonra a számelmélet fogja megadni a választ a következő fejezetekben. A számelmélet évezredekig a matematikának látszólag egy haszontalan területe volt. A 20. század második felére azonban az információs társadalom alapjává vált. Már most megemlítjük azonban, hogy ebben kulcsfontosságú szerepet játszik az úgynevezett prímfaktorizáció feladatának látszólagos algoritmikus nehézsége. Ezen áll vagy bukik ugyanis az egész. A prímszámokról és a prímfaktorizációról bőven lesz még szó a következő fejezetekben. Azt azonban mindenképpen fontosnak tartom megemlíteni ezen a ponton, hogy a prímfaktorizáció feladatáról még nem bizonyított, hogy NP-teljes lenne.

Babai eredménye után jogosan vetődik fel a kérdés: lehetséges, hogy a prímfaktorizáció problémája is a $P$ és az NP-teljes problémaosztály között helyezkedik el valahol? Netán egyenesen $P$ -beli? A választ nem tudjuk, de nagyon reméljük, hogy nem így van. Egy ilyen felfedezés ugyanis alapjaiban változtatná meg a jelenleg használt rejtjelezési eljárások biztonságába vetett hitünket. Ezen a ponton érdemes feltenni a kérdést, hogy vajon valóban senki nem tudja a választ? Vajon ha igenlő lenne a válasz, és valaki rájönne egy hatékony prímfaktorizációs algoritmusra, biztosan publikálná-e a tudományos közösség számára? Vagy megpróbálna inkább titokban hasznot húzni belőle? Az Olvasó vajon mit tenne?

Ebben a fejezetben tehát megismertük a Karp-redukció fogalmát, amelynek segítségével összehasonlíthatóvá válnak az algoritmikus problémák a nehézségük szempontjából. Definiáltuk az NP-teljes problémák osztályát, amelyekről ugyan nem tudjuk biztosan, hogy valóban olyan nehezek-e, mint amilyennek látszanak, de megmutattuk, hogy miért lenne rendkívül meglepő, ha mégsem ez lenne a helyzet. Most már van egy átfogó képünk arról, hogy mit tekintünk algoritmikusan "nehéz" vagy "könnyű" feladatnak. A 9. és a 10. fejezetekben felvázoljuk egy olyan rejtjelező rendszer alapjait, amellyel Alice és Bob meg tudja oldani a kulcsmegosztás problémáját anélkül, hogy személyesen találkozniuk kéne. Ez a rendszer továbbá az 5.5. szakaszban bemutatott Mallory, mint aktív támadó elleni védelemben is komoly szerepet játszik, mint azt látni fogjuk.